oj.uz

Submission #936085

# Submission time Handle Problem Language Result Execution time Memory
936085 2024-03-01T06:13:06 Z guagua0407 Bomb (IZhO17_bomb) C++17
10 / 100
 289 ms 4520 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()

const int mxn=505;
char c[mxn][mxn];
int pre[mxn][mxn];
bool used[mxn][mxn];
int mn[mxn];
int n,m;

bool check(int x,int y){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            used[i][j]=false;
        }
    }
    for(int j=1;j<=m;j++){
        mn[j]=0;
    }
    int cur=0;
    for(int i=y;i<=n;i++){
        int prv=0;
        for(int j=x;j<=m;j++){
            int sum=pre[i][j]-pre[i][j-x]-pre[i-y][j]+pre[i-y][j-x];
            if(sum!=x*y){
                continue;
            }
            for(int k=max(prv+1,j-x+1);k<=j;k++){
                for(int l=i;l>=max(mn[k]+1,i-y+1);l--){
                    used[l][k]=true;
                    cur++;
                }
                mn[k]=i;
            }
            prv=j;
        }
    }
    return cur==pre[n][m];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    auto st=clock();
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            pre[i][j]=pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1]+(c[i][j]=='1');
        }
    }
    int ans=0;
    int r=n;
    for(int len=1;len<=m;len++){
        while(r>=1 and !check(len,r)){
            r--;
        }
        //cout<<r<<'\n';
        ans+=r;
    }
    cout<<ans<<'\n';
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:49:10: warning: unused variable 'st' [-Wunused-variable]
   49 |     auto st=clock();
      |          ^~

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Runtime error 3 ms 2908 KB Execution killed with signal 11
4 Runtime error 3 ms 2908 KB Execution killed with signal 11
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Incorrect 1 ms 464 KB Output isn't correct
19 Incorrect 2 ms 604 KB Output isn't correct
20 Incorrect 1 ms 604 KB Output isn't correct
21 Incorrect 1 ms 604 KB Output isn't correct
22 Incorrect 1 ms 468 KB Output isn't correct
23 Incorrect 2 ms 604 KB Output isn't correct
24 Incorrect 1 ms 604 KB Output isn't correct
25 Incorrect 2 ms 604 KB Output isn't correct
26 Correct 4 ms 600 KB Output is correct
27 Correct 57 ms 1368 KB Output is correct
28 Incorrect 22 ms 1372 KB Output isn't correct
29 Incorrect 143 ms 1624 KB Output isn't correct
30 Incorrect 103 ms 1880 KB Output isn't correct
31 Incorrect 62 ms 1588 KB Output isn't correct
32 Incorrect 69 ms 1812 KB Output isn't correct
33 Incorrect 140 ms 1884 KB Output isn't correct
34 Incorrect 26 ms 1372 KB Output isn't correct
35 Incorrect 96 ms 1884 KB Output isn't correct
36 Correct 289 ms 1880 KB Output is correct
37 Incorrect 0 ms 348 KB Output isn't correct
38 Runtime error 14 ms 4380 KB Execution killed with signal 11
39 Incorrect 0 ms 600 KB Output isn't correct
40 Runtime error 6 ms 3700 KB Execution killed with signal 11
41 Incorrect 0 ms 344 KB Output isn't correct
42 Incorrect 3 ms 604 KB Output isn't correct
43 Runtime error 19 ms 4440 KB Execution killed with signal 11
44 Incorrect 204 ms 1980 KB Output isn't correct
45 Runtime error 14 ms 4440 KB Execution killed with signal 11
46 Runtime error 14 ms 4444 KB Execution killed with signal 11
47 Runtime error 14 ms 4332 KB Execution killed with signal 11
48 Runtime error 16 ms 4336 KB Execution killed with signal 11
49 Runtime error 18 ms 4444 KB Execution killed with signal 11
50 Runtime error 14 ms 4408 KB Execution killed with signal 11
51 Runtime error 14 ms 4440 KB Execution killed with signal 11
52 Runtime error 14 ms 4444 KB Execution killed with signal 11
53 Runtime error 14 ms 4440 KB Execution killed with signal 11
54 Runtime error 14 ms 4444 KB Execution killed with signal 11
55 Runtime error 14 ms 4296 KB Execution killed with signal 11
56 Runtime error 15 ms 4444 KB Execution killed with signal 11
57 Runtime error 14 ms 4324 KB Execution killed with signal 11
58 Runtime error 14 ms 4444 KB Execution killed with signal 11
59 Runtime error 14 ms 4444 KB Execution killed with signal 11
60 Runtime error 14 ms 4432 KB Execution killed with signal 11
61 Runtime error 14 ms 4312 KB Execution killed with signal 11
62 Runtime error 17 ms 4440 KB Execution killed with signal 11
63 Runtime error 14 ms 4440 KB Execution killed with signal 11
64 Runtime error 14 ms 4440 KB Execution killed with signal 11
65 Runtime error 15 ms 4444 KB Execution killed with signal 11
66 Runtime error 14 ms 4440 KB Execution killed with signal 11
67 Runtime error 14 ms 4380 KB Execution killed with signal 11
68 Runtime error 15 ms 4440 KB Execution killed with signal 11
69 Runtime error 14 ms 4440 KB Execution killed with signal 11
70 Runtime error 12 ms 4208 KB Execution killed with signal 11
71 Runtime error 16 ms 4440 KB Execution killed with signal 11
72 Runtime error 14 ms 4288 KB Execution killed with signal 11
73 Runtime error 14 ms 4420 KB Execution killed with signal 11
74 Runtime error 14 ms 4444 KB Execution killed with signal 11
75 Runtime error 14 ms 4316 KB Execution killed with signal 11
76 Runtime error 14 ms 4440 KB Execution killed with signal 11
77 Runtime error 14 ms 4296 KB Execution killed with signal 11
78 Runtime error 14 ms 4444 KB Execution killed with signal 11
79 Runtime error 14 ms 4436 KB Execution killed with signal 11
80 Runtime error 14 ms 4444 KB Execution killed with signal 11
81 Runtime error 16 ms 4520 KB Execution killed with signal 11
82 Runtime error 15 ms 4376 KB Execution killed with signal 11
83 Runtime error 14 ms 4444 KB Execution killed with signal 11
84 Runtime error 14 ms 4444 KB Execution killed with signal 11
85 Runtime error 14 ms 4444 KB Execution killed with signal 11
86 Runtime error 14 ms 4444 KB Execution killed with signal 11
87 Runtime error 14 ms 4496 KB Execution killed with signal 11
88 Runtime error 14 ms 4508 KB Execution killed with signal 11
89 Runtime error 14 ms 4444 KB Execution killed with signal 11
90 Runtime error 12 ms 4188 KB Execution killed with signal 11
91 Runtime error 14 ms 4444 KB Execution killed with signal 11
92 Runtime error 14 ms 4444 KB Execution killed with signal 11
93 Runtime error 14 ms 4344 KB Execution killed with signal 11
94 Runtime error 14 ms 4440 KB Execution killed with signal 11
95 Runtime error 14 ms 4440 KB Execution killed with signal 11
96 Runtime error 14 ms 4444 KB Execution killed with signal 11
97 Runtime error 14 ms 4444 KB Execution killed with signal 11
98 Runtime error 14 ms 4392 KB Execution killed with signal 11
99 Runtime error 14 ms 4420 KB Execution killed with signal 11
100 Runtime error 14 ms 4432 KB Execution killed with signal 11