답안 #39233 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39233	2018-01-10T11:14:10 Z	yerkimbekov	Bomb (IZhO17_bomb)	C++14	21 / 100	1000 ms	51200 KB

bomb

#include <bits/stdc++.h>
using namespace std;
 
int m,n,res=0,a[2505][2505],F[2505][2505];
 
int Suma(int u1,int v1,int u2,int v2)
{
    return a[u2][v2]-a[u1-1][v2]-a[u2][v1-1]+a[u1-1][v1-1];
}
 
int SumF(int u1,int v1,int u2,int v2)
{
    return F[u2][v2]-F[u1-1][v2]-F[u2][v1-1]+F[u1-1][v1-1];
}
 
bool Check(int mm,int nn)
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            F[i][j]=0;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            F[i][j]=F[i-1][j]+F[i][j-1]-F[i-1][j-1];
            if(i+mm-1<=m&&j+nn-1&&Suma(i,j,i+mm-1,j+nn-1)==mm*nn)
                F[i][j]++;
        }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(Suma(i,j,i,j)==1&&SumF(max(i-mm+1,1),max(j-nn+1,1),i,j)==0)
                return false;
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>m>>n;
    char c;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>c;
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+(c=='1');
        }
    int ll = 1, rr = m;
    while(ll <= rr){
      int i = (ll + rr) >> 1;
      bool tr = 0;
        int l=1,r=n;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(Check(i,mid)==true)
            {
                tr = 1;
                res=max(res,i*mid);
                l=mid+1;
            }
            else
                r=mid-1;
        }
      if(tr){
        ll = i + 1;
      }else{
        rr = i - 1;
      }
    }
    cout << res;
}

Subtask #1
21.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	51200 KB	Output is correct
2	Correct	0 ms	51200 KB	Output is correct
3	Correct	9 ms	51200 KB	Output is correct
4	Correct	6 ms	51200 KB	Output is correct
5	Correct	0 ms	51200 KB	Output is correct
6	Correct	0 ms	51200 KB	Output is correct
7	Correct	0 ms	51200 KB	Output is correct
8	Correct	0 ms	51200 KB	Output is correct
9	Incorrect	0 ms	51200 KB	Output isn't correct
10	Correct	0 ms	51200 KB	Output is correct
11	Incorrect	0 ms	51200 KB	Output isn't correct
12	Correct	0 ms	51200 KB	Output is correct
13	Correct	0 ms	51200 KB	Output is correct
14	Correct	0 ms	51200 KB	Output is correct
15	Incorrect	0 ms	51200 KB	Output isn't correct
16	Correct	0 ms	51200 KB	Output is correct
17	Correct	0 ms	51200 KB	Output is correct
18	Incorrect	0 ms	51200 KB	Output isn't correct
19	Incorrect	0 ms	51200 KB	Output isn't correct
20	Incorrect	3 ms	51200 KB	Output isn't correct
21	Correct	0 ms	51200 KB	Output is correct
22	Correct	3 ms	51200 KB	Output is correct
23	Incorrect	3 ms	51200 KB	Output isn't correct
24	Incorrect	0 ms	51200 KB	Output isn't correct
25	Incorrect	3 ms	51200 KB	Output isn't correct
26	Correct	0 ms	51200 KB	Output is correct
27	Correct	23 ms	51200 KB	Output is correct
28	Correct	39 ms	51200 KB	Output is correct
29	Incorrect	53 ms	51200 KB	Output isn't correct
30	Incorrect	73 ms	51200 KB	Output isn't correct
31	Incorrect	49 ms	51200 KB	Output isn't correct
32	Incorrect	56 ms	51200 KB	Output isn't correct
33	Incorrect	63 ms	51200 KB	Output isn't correct
34	Incorrect	23 ms	51200 KB	Output isn't correct
35	Incorrect	69 ms	51200 KB	Output isn't correct
36	Correct	93 ms	51200 KB	Output is correct
37	Incorrect	0 ms	51200 KB	Output isn't correct
38	Execution timed out	1000 ms	51200 KB	Execution timed out
39	Incorrect	0 ms	51200 KB	Output isn't correct
40	Incorrect	439 ms	51200 KB	Output isn't correct
41	Correct	0 ms	51200 KB	Output is correct
42	Incorrect	0 ms	51200 KB	Output isn't correct
43	Execution timed out	1000 ms	51200 KB	Execution timed out
44	Incorrect	93 ms	51200 KB	Output isn't correct
45	Execution timed out	1000 ms	51200 KB	Execution timed out
46	Execution timed out	1000 ms	51200 KB	Execution timed out
47	Execution timed out	1000 ms	51200 KB	Execution timed out
48	Execution timed out	1000 ms	51200 KB	Execution timed out
49	Execution timed out	1000 ms	51200 KB	Execution timed out
50	Execution timed out	1000 ms	51200 KB	Execution timed out
51	Execution timed out	1000 ms	51200 KB	Execution timed out
52	Execution timed out	1000 ms	51200 KB	Execution timed out
53	Execution timed out	1000 ms	51200 KB	Execution timed out
54	Execution timed out	1000 ms	51200 KB	Execution timed out
55	Execution timed out	1000 ms	51200 KB	Execution timed out
56	Execution timed out	1000 ms	51200 KB	Execution timed out
57	Execution timed out	1000 ms	51200 KB	Execution timed out
58	Execution timed out	1000 ms	51200 KB	Execution timed out
59	Execution timed out	1000 ms	51200 KB	Execution timed out
60	Execution timed out	1000 ms	51200 KB	Execution timed out
61	Execution timed out	1000 ms	51200 KB	Execution timed out
62	Execution timed out	1000 ms	51200 KB	Execution timed out
63	Execution timed out	1000 ms	51200 KB	Execution timed out
64	Execution timed out	1000 ms	51200 KB	Execution timed out
65	Execution timed out	1000 ms	51200 KB	Execution timed out
66	Execution timed out	1000 ms	51200 KB	Execution timed out
67	Execution timed out	1000 ms	51200 KB	Execution timed out
68	Execution timed out	1000 ms	51200 KB	Execution timed out
69	Execution timed out	1000 ms	51200 KB	Execution timed out
70	Execution timed out	1000 ms	51200 KB	Execution timed out
71	Execution timed out	1000 ms	51200 KB	Execution timed out
72	Execution timed out	1000 ms	51200 KB	Execution timed out
73	Execution timed out	1000 ms	51200 KB	Execution timed out
74	Execution timed out	1000 ms	51200 KB	Execution timed out
75	Execution timed out	1000 ms	51200 KB	Execution timed out
76	Execution timed out	1000 ms	51200 KB	Execution timed out
77	Execution timed out	1000 ms	51200 KB	Execution timed out
78	Execution timed out	1000 ms	51200 KB	Execution timed out
79	Execution timed out	1000 ms	51200 KB	Execution timed out
80	Execution timed out	1000 ms	51200 KB	Execution timed out
81	Execution timed out	1000 ms	51200 KB	Execution timed out
82	Execution timed out	1000 ms	51200 KB	Execution timed out
83	Execution timed out	1000 ms	51200 KB	Execution timed out
84	Execution timed out	1000 ms	51200 KB	Execution timed out
85	Execution timed out	1000 ms	51200 KB	Execution timed out
86	Execution timed out	1000 ms	51200 KB	Execution timed out
87	Execution timed out	1000 ms	51200 KB	Execution timed out
88	Execution timed out	1000 ms	51200 KB	Execution timed out
89	Execution timed out	1000 ms	51200 KB	Execution timed out
90	Execution timed out	1000 ms	51200 KB	Execution timed out
91	Execution timed out	1000 ms	51200 KB	Execution timed out
92	Execution timed out	1000 ms	51200 KB	Execution timed out
93	Execution timed out	1000 ms	51200 KB	Execution timed out
94	Execution timed out	1000 ms	51200 KB	Execution timed out
95	Execution timed out	1000 ms	51200 KB	Execution timed out
96	Execution timed out	1000 ms	51200 KB	Execution timed out
97	Execution timed out	1000 ms	51200 KB	Execution timed out
98	Execution timed out	1000 ms	51200 KB	Execution timed out
99	Execution timed out	1000 ms	51200 KB	Execution timed out
100	Execution timed out	1000 ms	51200 KB	Execution timed out

답안 #39233

Compilation message

Subtask #1 21.0 / 100.0

Subtask #1
21.0 / 100.0