Submission #171770

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
171770	2019-12-30T10:58:01 Z	mosiashvililuka	Bomb (IZhO17_bomb)	C++14	51 / 100	1000 ms	26692 KB

bomb

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,dp[2509][2509],zx,xc,qw,we,k[2509][2509],pas,dd,mxa,mxb;
string s;
bool f[2509][2509];
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>b;
    for(c=1; c<=a; c++){
        cin>>s;
        for(d=1; d<=b; d++){
            f[c][d]=s[d-1]-'0';
        }
    }
    if(a*b>=1000000){
    mxb=mxa=a+b+2;
        for(c=1; c<=a; c++){
        	zx=0;
        	for(d=1; d<=b; d++){
        		if(f[c][d]==1){
        			zx++;
				}else{
				    if(zx!=0) mxa=min(zx,mxa);
					zx=0;
				}
			}
			if(zx!=0) mxa=min(zx,mxa);
		}
		for(d=1; d<=b; d++){
			xc=0;
			for(c=1; c<=a; c++){
				if(f[c][d]==1){
					xc++;
				}else{
				    if(xc!=0) mxb=min(mxb,xc);
					xc=0;
				}
			}
			if(xc!=0) mxb=min(mxb,xc);
		}
		cout<<mxa*mxb;
        return 0;
    }
    for(c=1; c<=a; c++){
        for(d=1; d<=b; d++) dp[c][d]=dp[c-1][d]+dp[c][d-1]-dp[c-1][d-1]+f[c][d];
    }
    d=b;
    for(c=1; c<=a; c++){
        while(d>=1){
            bool bo=0;
            for(i=1; i<=a; i++) for(j=1; j<=b; j++) k[i][j]=0;
            for(i=c; i<=a; i++){
                for(j=d; j<=b; j++){
                    qw=i-c+1;we=j-d+1;
                    if(dp[i][j]-dp[i][we-1]-dp[qw-1][j]+dp[qw-1][we-1]==c*d){
                        k[qw][we]=1;
                    }
                }
            }
/*            if(c==2&&d==2){
                for(i=1; i<=a; i++){
                    for(j=1; j<=b; j++) cout<<k[i][j]<<" ";
                    cout<<endl;
                }
            }
            if(c==2&&d==2) cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl;*/
            for(i=1; i<=a; i++){
                for(j=1; j<=b; j++) k[i][j]=k[i-1][j]+k[i][j-1]-k[i-1][j-1]+k[i][j];
            }
/*            if(c==2&&d==2){
                for(i=1; i<=a; i++){
                    for(j=1; j<=b; j++) cout<<k[i][j]<<" ";
                    cout<<endl;
                }
            }*/
            for(i=1; i<=a; i++){
                if(bo==1) break;
                for(j=1; j<=b; j++){
                    if(f[i][j]==0) continue;
                    qw=i-c+1;we=j-d+1;
                    if(qw<=0) qw=1;
                    if(we<=0) we=1;
                    int hj=0;
                    hj=k[i][j]-k[qw-1][j]-k[i][we-1]+k[qw-1][we-1];
                    if(hj==0){
                        bo=1;
                        break;
                    }
                }
            }
            if(bo==0){
//                cout<<c<<" "<<d<<" vict"<<endl;
                if(pas<c*d) pas=c*d;
                break;
            }
  //          cout<<c<<" "<<d<<" lose"<<endl;
            d--;
        }
    }
    cout<<pas;
    return 0;
}

Subtask #1

51.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	33 ms	26616 KB	Output is correct
4	Correct	36 ms	26692 KB	Output is correct
5	Correct	31 ms	376 KB	Output is correct
6	Correct	7 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Correct	2 ms	632 KB	Output is correct
10	Correct	2 ms	532 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	504 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	2 ms	508 KB	Output is correct
16	Correct	2 ms	632 KB	Output is correct
17	Correct	4 ms	1016 KB	Output is correct
18	Correct	5 ms	1272 KB	Output is correct
19	Correct	7 ms	1400 KB	Output is correct
20	Correct	7 ms	1400 KB	Output is correct
21	Correct	5 ms	1016 KB	Output is correct
22	Correct	6 ms	1172 KB	Output is correct
23	Correct	9 ms	1528 KB	Output is correct
24	Correct	6 ms	1272 KB	Output is correct
25	Correct	10 ms	1528 KB	Output is correct
26	Correct	9 ms	1528 KB	Output is correct
27	Correct	110 ms	4188 KB	Output is correct
28	Correct	210 ms	4472 KB	Output is correct
29	Correct	278 ms	5624 KB	Output is correct
30	Correct	536 ms	6648 KB	Output is correct
31	Correct	413 ms	5240 KB	Output is correct
32	Correct	404 ms	6016 KB	Output is correct
33	Correct	646 ms	6904 KB	Output is correct
34	Correct	101 ms	4896 KB	Output is correct
35	Correct	470 ms	6776 KB	Output is correct
36	Correct	567 ms	6820 KB	Output is correct
37	Correct	2 ms	504 KB	Output is correct
38	Correct	37 ms	12332 KB	Output is correct
39	Correct	2 ms	632 KB	Output is correct
40	Execution timed out	1077 ms	16376 KB	Time limit exceeded
41	Correct	2 ms	504 KB	Output is correct
42	Correct	12 ms	1528 KB	Output is correct
43	Correct	41 ms	12536 KB	Output is correct
44	Correct	788 ms	6904 KB	Output is correct
45	Incorrect	42 ms	11384 KB	Output isn't correct
46	Correct	45 ms	12660 KB	Output is correct
47	Incorrect	41 ms	12664 KB	Output isn't correct
48	Incorrect	43 ms	10660 KB	Output isn't correct
49	Correct	42 ms	12152 KB	Output is correct
50	Incorrect	47 ms	12660 KB	Output isn't correct
51	Incorrect	44 ms	12536 KB	Output isn't correct
52	Incorrect	43 ms	11640 KB	Output isn't correct
53	Incorrect	43 ms	12664 KB	Output isn't correct
54	Incorrect	43 ms	12408 KB	Output isn't correct
55	Incorrect	40 ms	12536 KB	Output isn't correct
56	Correct	40 ms	12544 KB	Output is correct
57	Incorrect	43 ms	12692 KB	Output isn't correct
58	Incorrect	41 ms	12540 KB	Output isn't correct
59	Incorrect	44 ms	12536 KB	Output isn't correct
60	Correct	40 ms	12536 KB	Output is correct
61	Correct	38 ms	12536 KB	Output is correct
62	Correct	42 ms	12664 KB	Output is correct
63	Correct	39 ms	12664 KB	Output is correct
64	Correct	42 ms	12536 KB	Output is correct
65	Incorrect	40 ms	12664 KB	Output isn't correct
66	Incorrect	42 ms	12152 KB	Output isn't correct
67	Incorrect	42 ms	12772 KB	Output isn't correct
68	Incorrect	38 ms	12536 KB	Output isn't correct
69	Incorrect	43 ms	12656 KB	Output isn't correct
70	Incorrect	25 ms	9208 KB	Output isn't correct
71	Incorrect	42 ms	12536 KB	Output isn't correct
72	Incorrect	41 ms	11768 KB	Output isn't correct
73	Incorrect	42 ms	12564 KB	Output isn't correct
74	Incorrect	41 ms	12540 KB	Output isn't correct
75	Incorrect	47 ms	12712 KB	Output isn't correct
76	Incorrect	42 ms	11224 KB	Output isn't correct
77	Incorrect	43 ms	12536 KB	Output isn't correct
78	Incorrect	45 ms	11280 KB	Output isn't correct
79	Incorrect	42 ms	12536 KB	Output isn't correct
80	Incorrect	45 ms	12664 KB	Output isn't correct
81	Incorrect	43 ms	12536 KB	Output isn't correct
82	Incorrect	42 ms	12664 KB	Output isn't correct
83	Incorrect	42 ms	12692 KB	Output isn't correct
84	Incorrect	43 ms	12536 KB	Output isn't correct
85	Incorrect	42 ms	12664 KB	Output isn't correct
86	Incorrect	41 ms	12540 KB	Output isn't correct
87	Incorrect	41 ms	12640 KB	Output isn't correct
88	Incorrect	43 ms	12656 KB	Output isn't correct
89	Incorrect	38 ms	12536 KB	Output isn't correct
90	Incorrect	25 ms	9208 KB	Output isn't correct
91	Incorrect	46 ms	12792 KB	Output isn't correct
92	Incorrect	39 ms	12536 KB	Output isn't correct
93	Incorrect	40 ms	12664 KB	Output isn't correct
94	Incorrect	41 ms	12588 KB	Output isn't correct
95	Incorrect	44 ms	12664 KB	Output isn't correct
96	Incorrect	43 ms	12548 KB	Output isn't correct
97	Incorrect	41 ms	12664 KB	Output isn't correct
98	Incorrect	42 ms	12664 KB	Output isn't correct
99	Incorrect	43 ms	12664 KB	Output isn't correct
100	Incorrect	40 ms	12664 KB	Output isn't correct