oj.uz

Submission #920207

# Submission time Handle Problem Language Result Execution time Memory
920207 2024-02-02T09:23:57 Z MilosMilutinovic Bomb (IZhO17_bomb) C++14
47 / 100
 1000 ms 51548 KB 
// Online C++ compiler to run C++ program online
#include<bits/stdc++.h>

using namespace std;

int n,m;
char s[2505];
int v[2505][2505],a[2505][2505];
bool was[2505][2505];

int queryA(int x1,int y1,int x2,int y2){
    return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}

int queryV(int x1,int y1,int x2,int y2){
    return v[x2][y2]-v[x1-1][y2]-v[x2][y1-1]+v[x1-1][y1-1];
}

bool check(int x,int y){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            v[i][j]=0;
        }
    }
    for(int i=1;i+x<=n+1;i++){
        for(int j=1;j+y<=m+1;j++){
            if(queryA(i,j,i+x-1,j+y-1)==x*y){
                v[i][j]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            v[i][j]+=v[i-1][j];
            v[i][j]+=v[i][j-1];
            v[i][j]-=v[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(queryA(i,j,i,j)==1&&queryV(max(1,i-x+1),max(1,j-y+1),i,j)==0){
                return false;
            }
        }
    }
    return true;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++){
            a[i][j]=(int)(s[j]-'0');
            a[i][j]+=a[i-1][j];
            a[i][j]+=a[i][j-1];
            a[i][j]-=a[i-1][j-1];
        }
    }
    int lx=n;
    int ly=m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(queryA(i,j,i,j)==0) continue;
            int ptr=j;
            while(ptr+1<=m&&queryA(i,ptr+1,i,ptr+1)==1) ptr++;
            ly=min(ly,ptr-j+1);
            j=ptr;
        }
    }
    for(int j=1;j<=m;j++){ 
        for(int i=1;i<=n;i++){
            if(queryA(i,j,i,j)==0) continue;
            int ptr=i;
            while(ptr+1<=n&&queryA(ptr+1,j,ptr+1,j)==1) ptr++;
            lx=min(lx,ptr-i+1);
            i=ptr;
        }
    }
    int ans=0;
    for(int x=lx;x>=1;x--){
        int l=1,r=ly;
        while(l<=r){
            int mid=(l+r)/2;
            if(x*mid<=ans||check(x,mid)) ans=max(ans,x*mid),l=mid+1; else r=mid-1;
        }
        int low=1,high=x-1,nxt=0;
        while(low<=high){
            int mid=(low+high)/2;
            if((ans+mid)/mid<=ly&&check(mid,(ans+mid)/mid)) nxt=mid,low=mid+1; else high=mid-1;
        }
        x=nxt;
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
bomb.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%s",s+1);
      |         ~~~~~^~~~~~~~~~

Subtask #1
47.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 10 ms 50264 KB Output is correct
4 Correct 8 ms 50264 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Incorrect 1 ms 4440 KB Output isn't correct
10 Correct 1 ms 4444 KB Output is correct
11 Incorrect 1 ms 4440 KB Output isn't correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Incorrect 1 ms 4440 KB Output isn't correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 8536 KB Output is correct
18 Correct 2 ms 8536 KB Output is correct
19 Incorrect 2 ms 8536 KB Output isn't correct
20 Incorrect 2 ms 8536 KB Output isn't correct
21 Correct 2 ms 8536 KB Output is correct
22 Correct 2 ms 8536 KB Output is correct
23 Incorrect 2 ms 8536 KB Output isn't correct
24 Incorrect 2 ms 8540 KB Output isn't correct
25 Incorrect 2 ms 8536 KB Output isn't correct
26 Correct 2 ms 8796 KB Output is correct
27 Correct 4 ms 12636 KB Output is correct
28 Correct 8 ms 12632 KB Output is correct
29 Incorrect 39 ms 12632 KB Output isn't correct
30 Incorrect 23 ms 12636 KB Output isn't correct
31 Incorrect 17 ms 12888 KB Output isn't correct
32 Incorrect 16 ms 12632 KB Output isn't correct
33 Incorrect 23 ms 16732 KB Output isn't correct
34 Incorrect 5 ms 12632 KB Output isn't correct
35 Incorrect 21 ms 16728 KB Output isn't correct
36 Correct 11 ms 16728 KB Output is correct
37 Correct 1 ms 4440 KB Output is correct
38 Correct 526 ms 51284 KB Output is correct
39 Incorrect 1 ms 4440 KB Output isn't correct
40 Incorrect 113 ms 25048 KB Output isn't correct
41 Correct 1 ms 4440 KB Output is correct
42 Incorrect 5 ms 8536 KB Output isn't correct
43 Correct 436 ms 51404 KB Output is correct
44 Incorrect 277 ms 17088 KB Output isn't correct
45 Execution timed out 1025 ms 51144 KB Time limit exceeded
46 Correct 252 ms 51284 KB Output is correct
47 Execution timed out 1024 ms 51412 KB Time limit exceeded
48 Correct 329 ms 51536 KB Output is correct
49 Correct 191 ms 51280 KB Output is correct
50 Correct 371 ms 51280 KB Output is correct
51 Correct 370 ms 51280 KB Output is correct
52 Correct 319 ms 51548 KB Output is correct
53 Correct 322 ms 51280 KB Output is correct
54 Correct 323 ms 51160 KB Output is correct
55 Correct 322 ms 51280 KB Output is correct
56 Correct 293 ms 51348 KB Output is correct
57 Correct 354 ms 51416 KB Output is correct
58 Correct 353 ms 51280 KB Output is correct
59 Correct 310 ms 51516 KB Output is correct
60 Correct 256 ms 51280 KB Output is correct
61 Correct 286 ms 51280 KB Output is correct
62 Correct 410 ms 51352 KB Output is correct
63 Correct 514 ms 51280 KB Output is correct
64 Correct 353 ms 51280 KB Output is correct
65 Correct 280 ms 51352 KB Output is correct
66 Correct 423 ms 51540 KB Output is correct
67 Correct 360 ms 51352 KB Output is correct
68 Correct 430 ms 51536 KB Output is correct
69 Correct 355 ms 51280 KB Output is correct
70 Incorrect 572 ms 45504 KB Output isn't correct
71 Incorrect 899 ms 51472 KB Output isn't correct
72 Incorrect 884 ms 51348 KB Output isn't correct
73 Execution timed out 1016 ms 51420 KB Time limit exceeded
74 Execution timed out 1037 ms 51284 KB Time limit exceeded
75 Incorrect 993 ms 51352 KB Output isn't correct
76 Execution timed out 1035 ms 51280 KB Time limit exceeded
77 Execution timed out 1006 ms 51348 KB Time limit exceeded
78 Execution timed out 1038 ms 51280 KB Time limit exceeded
79 Incorrect 579 ms 51352 KB Output isn't correct
80 Incorrect 544 ms 51160 KB Output isn't correct
81 Incorrect 745 ms 51536 KB Output isn't correct
82 Incorrect 1000 ms 51348 KB Output isn't correct
83 Execution timed out 1036 ms 51280 KB Time limit exceeded
84 Incorrect 687 ms 51128 KB Output isn't correct
85 Incorrect 983 ms 51536 KB Output isn't correct
86 Incorrect 681 ms 51352 KB Output isn't correct
87 Incorrect 576 ms 51164 KB Output isn't correct
88 Incorrect 990 ms 51536 KB Output isn't correct
89 Incorrect 901 ms 51352 KB Output isn't correct
90 Incorrect 656 ms 45772 KB Output isn't correct
91 Incorrect 960 ms 51352 KB Output isn't correct
92 Incorrect 891 ms 51156 KB Output isn't correct
93 Incorrect 596 ms 51148 KB Output isn't correct
94 Incorrect 876 ms 51352 KB Output isn't correct
95 Execution timed out 1034 ms 51160 KB Time limit exceeded
96 Incorrect 988 ms 51352 KB Output isn't correct
97 Incorrect 606 ms 51160 KB Output isn't correct
98 Execution timed out 1006 ms 51416 KB Time limit exceeded
99 Incorrect 908 ms 51280 KB Output isn't correct
100 Incorrect 607 ms 51348 KB Output isn't correct