Submission #171748

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
171748	2019-12-30T09:16:33 Z	mosiashvililuka	Bomb (IZhO17_bomb)	C++14	47 / 100	1000 ms	26656 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){
        for(c=1; c<=a; c++){
        	zx=0;
        	mxb=mxa=a+b+2;
        	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

47.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	632 KB	Output is correct
3	Correct	32 ms	26616 KB	Output is correct
4	Correct	35 ms	26656 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	632 KB	Output is correct
9	Correct	2 ms	632 KB	Output is correct
10	Correct	2 ms	508 KB	Output is correct
11	Correct	2 ms	632 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	504 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	4 ms	1144 KB	Output is correct
18	Correct	4 ms	1144 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	1272 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	111 ms	4216 KB	Output is correct
28	Correct	211 ms	4472 KB	Output is correct
29	Correct	279 ms	5624 KB	Output is correct
30	Correct	536 ms	6648 KB	Output is correct
31	Correct	406 ms	5340 KB	Output is correct
32	Correct	406 ms	6136 KB	Output is correct
33	Correct	647 ms	7032 KB	Output is correct
34	Correct	101 ms	4984 KB	Output is correct
35	Correct	468 ms	7032 KB	Output is correct
36	Correct	565 ms	6904 KB	Output is correct
37	Correct	2 ms	632 KB	Output is correct
38	Correct	39 ms	12536 KB	Output is correct
39	Correct	2 ms	504 KB	Output is correct
40	Execution timed out	1080 ms	16312 KB	Time limit exceeded
41	Correct	2 ms	504 KB	Output is correct
42	Correct	12 ms	1592 KB	Output is correct
43	Correct	40 ms	12536 KB	Output is correct
44	Correct	774 ms	6776 KB	Output is correct
45	Incorrect	39 ms	12536 KB	Output isn't correct
46	Correct	44 ms	12792 KB	Output is correct
47	Incorrect	40 ms	12544 KB	Output isn't correct
48	Incorrect	39 ms	12664 KB	Output isn't correct
49	Incorrect	39 ms	12664 KB	Output isn't correct
50	Incorrect	42 ms	12636 KB	Output isn't correct
51	Incorrect	40 ms	12664 KB	Output isn't correct
52	Incorrect	40 ms	12664 KB	Output isn't correct
53	Incorrect	41 ms	12544 KB	Output isn't correct
54	Incorrect	38 ms	12664 KB	Output isn't correct
55	Incorrect	41 ms	12548 KB	Output isn't correct
56	Correct	40 ms	12532 KB	Output is correct
57	Incorrect	39 ms	12664 KB	Output isn't correct
58	Incorrect	40 ms	12660 KB	Output isn't correct
59	Incorrect	42 ms	12540 KB	Output isn't correct
60	Correct	39 ms	12664 KB	Output is correct
61	Incorrect	35 ms	12664 KB	Output isn't correct
62	Incorrect	38 ms	12720 KB	Output isn't correct
63	Incorrect	34 ms	12664 KB	Output isn't correct
64	Correct	40 ms	12536 KB	Output is correct
65	Incorrect	38 ms	12536 KB	Output isn't correct
66	Incorrect	39 ms	12660 KB	Output isn't correct
67	Incorrect	36 ms	12536 KB	Output isn't correct
68	Incorrect	39 ms	12664 KB	Output isn't correct
69	Incorrect	41 ms	12528 KB	Output isn't correct
70	Incorrect	26 ms	9212 KB	Output isn't correct
71	Incorrect	41 ms	12536 KB	Output isn't correct
72	Incorrect	39 ms	12536 KB	Output isn't correct
73	Incorrect	39 ms	12536 KB	Output isn't correct
74	Incorrect	42 ms	12664 KB	Output isn't correct
75	Incorrect	37 ms	12536 KB	Output isn't correct
76	Incorrect	38 ms	12668 KB	Output isn't correct
77	Incorrect	37 ms	12664 KB	Output isn't correct
78	Incorrect	44 ms	12660 KB	Output isn't correct
79	Incorrect	39 ms	12536 KB	Output isn't correct
80	Incorrect	40 ms	12536 KB	Output isn't correct
81	Incorrect	46 ms	12792 KB	Output isn't correct
82	Incorrect	51 ms	12540 KB	Output isn't correct
83	Incorrect	52 ms	12664 KB	Output isn't correct
84	Incorrect	55 ms	12664 KB	Output isn't correct
85	Incorrect	41 ms	12664 KB	Output isn't correct
86	Incorrect	40 ms	12536 KB	Output isn't correct
87	Incorrect	41 ms	12536 KB	Output isn't correct
88	Incorrect	41 ms	12536 KB	Output isn't correct
89	Incorrect	42 ms	12648 KB	Output isn't correct
90	Incorrect	24 ms	9208 KB	Output isn't correct
91	Incorrect	39 ms	12664 KB	Output isn't correct
92	Incorrect	47 ms	12536 KB	Output isn't correct
93	Incorrect	43 ms	12664 KB	Output isn't correct
94	Incorrect	44 ms	12536 KB	Output isn't correct
95	Incorrect	42 ms	12664 KB	Output isn't correct
96	Incorrect	39 ms	12664 KB	Output isn't correct
97	Incorrect	41 ms	12764 KB	Output isn't correct
98	Incorrect	39 ms	12564 KB	Output isn't correct
99	Incorrect	43 ms	12540 KB	Output isn't correct
100	Incorrect	39 ms	12540 KB	Output isn't correct