oj.uz

Submission #37407

# Submission time Handle Problem Language Result Execution time Memory
37407 2017-12-25T06:54:46 Z top34051 Bomb (IZhO17_bomb) C++14
21 / 100
 1000 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 2505;

int n,m;
int p[maxn][maxn];
vector<pii> con[maxn];
set<pii> itv[maxn];
multiset<int> len;

void upd(int x,pii val,int type) {
    if(type==0) {
//        printf("DEL [%d, %d]\n",val.X,val.Y);
        len.erase(len.find(val.Y-val.X+1));
        itv[x].erase(val);
    }
    else {
//        printf("ADD [%d, %d]\n",val.X,val.Y);
        len.insert(val.Y-val.X+1);
        itv[x].insert(val);
    }
}
void add(int x,int y) {
    int l,r;
    set<pii>::iterator L,R;
    upd(x,{y,y},1);
    l = r = y;
    L = R = itv[x].find({y,y});
    if(L!=itv[x].begin()) {
        --L;
        if(L->Y+1==y) {
            l = L->X;
            upd(x,*L,0);
        }
    }
    ++R;
    if(R!=itv[x].end()) {
        if(R->X-1==y) {
            r = R->Y;
            upd(x,*R,0);
        }
    }
    upd(x,{y,y},0);
    upd(x,{l,r},1);
}
void del(int x,int y) {
    int l,r;
    set<pii>::iterator it;
    it = itv[x].upper_bound({y,m+1});
    --it;
    l = it->X; r = it->Y;
    upd(x,{l,r},0);
    if(l<=y-1) upd(x,{l,y-1},1);
    if(y+1<=r) upd(x,{y+1,r},1);
}
int main() {
    int i,j,x,cnt,bound,ans;
    char c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) {
        for(j=1;j<=m;j++) {
            scanf(" %c",&c);
            p[i][j] = c-'0';
        }
    }
    bound = n;
    for(j=1;j<=m;j++) {
        cnt = 0;
        for(i=n;i>=1;i--) {
            if(p[i][j]==0) {
                if(cnt!=0) bound = min(bound, cnt);
                cnt = 0;
            }
            else cnt++;
            con[cnt].push_back({i,j});
        }
    }
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) add(i,j);
    ans = 0;
    for(x=1;x<=bound;x++) {
//        printf("Fixed row = %d\n",x);
        for(auto t : con[x-1]) del(t.X,t.Y);
//        for(i=1;i<=n;i++) {
//            printf("\t");
//            for(auto t : itv[i]) printf("[%d, %d] ",t.X,t.Y);
//            printf("\n");
//        }
        if(!len.empty()) ans = max(ans, x*(*len.begin()));
//        if(!len.empty()) printf("Minimum = %d\n",*len.begin());
    }
    printf("%d",ans);
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:63:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
bomb.cpp:66:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",&c);
                            ^

Subtask #1
21.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 26708 KB Output is correct
2 Correct 0 ms 26708 KB Output is correct
3 Correct 0 ms 26972 KB Output is correct
4 Correct 0 ms 26972 KB Output is correct
5 Correct 0 ms 26848 KB Output is correct
6 Correct 0 ms 26708 KB Output is correct
7 Correct 0 ms 26708 KB Output is correct
8 Correct 0 ms 26708 KB Output is correct
9 Incorrect 0 ms 26708 KB Output isn't correct
10 Correct 0 ms 26708 KB Output is correct
11 Correct 0 ms 26708 KB Output is correct
12 Correct 0 ms 26708 KB Output is correct
13 Correct 0 ms 26708 KB Output is correct
14 Correct 0 ms 26708 KB Output is correct
15 Correct 0 ms 26708 KB Output is correct
16 Correct 0 ms 26708 KB Output is correct
17 Incorrect 3 ms 26856 KB Output isn't correct
18 Correct 3 ms 26848 KB Output is correct
19 Correct 3 ms 26848 KB Output is correct
20 Incorrect 3 ms 26848 KB Output isn't correct
21 Correct 3 ms 26848 KB Output is correct
22 Correct 3 ms 26848 KB Output is correct
23 Incorrect 3 ms 26848 KB Output isn't correct
24 Incorrect 3 ms 26848 KB Output isn't correct
25 Incorrect 6 ms 26848 KB Output isn't correct
26 Incorrect 3 ms 26840 KB Output isn't correct
27 Incorrect 49 ms 27632 KB Output isn't correct
28 Correct 76 ms 28336 KB Output is correct
29 Incorrect 66 ms 28264 KB Output isn't correct
30 Incorrect 106 ms 30288 KB Output isn't correct
31 Incorrect 83 ms 28612 KB Output isn't correct
32 Incorrect 93 ms 30024 KB Output isn't correct
33 Incorrect 96 ms 30428 KB Output isn't correct
34 Correct 43 ms 28340 KB Output is correct
35 Incorrect 99 ms 29868 KB Output isn't correct
36 Incorrect 83 ms 28688 KB Output isn't correct
37 Incorrect 0 ms 26708 KB Output isn't correct
38 Execution timed out 1000 ms 106864 KB Execution timed out
39 Incorrect 0 ms 26708 KB Output isn't correct
40 Incorrect 429 ms 35096 KB Output isn't correct
41 Incorrect 0 ms 26708 KB Output isn't correct
42 Incorrect 3 ms 26840 KB Output isn't correct
43 Execution timed out 1000 ms 96980 KB Execution timed out
44 Incorrect 106 ms 29472 KB Output isn't correct
45 Execution timed out 1000 ms 124952 KB Execution timed out
46 Execution timed out 1000 ms 104336 KB Execution timed out
47 Execution timed out 1000 ms 125500 KB Execution timed out
48 Execution timed out 1000 ms 100520 KB Execution timed out
49 Execution timed out 1000 ms 106956 KB Execution timed out
50 Execution timed out 1000 ms 102736 KB Execution timed out
51 Execution timed out 1000 ms 102088 KB Execution timed out
52 Execution timed out 1000 ms 101120 KB Execution timed out
53 Execution timed out 1000 ms 100336 KB Execution timed out
54 Memory limit exceeded 569 ms 131072 KB Memory limit exceeded
55 Memory limit exceeded 533 ms 131072 KB Memory limit exceeded
56 Execution timed out 1000 ms 107936 KB Execution timed out
57 Memory limit exceeded 566 ms 131072 KB Memory limit exceeded
58 Memory limit exceeded 566 ms 131072 KB Memory limit exceeded
59 Memory limit exceeded 549 ms 131072 KB Memory limit exceeded
60 Execution timed out 1000 ms 96936 KB Execution timed out
61 Execution timed out 1000 ms 110152 KB Execution timed out
62 Execution timed out 1000 ms 108916 KB Execution timed out
63 Execution timed out 1000 ms 106864 KB Execution timed out
64 Memory limit exceeded 603 ms 131072 KB Memory limit exceeded
65 Execution timed out 1000 ms 100084 KB Execution timed out
66 Execution timed out 1000 ms 103084 KB Execution timed out
67 Execution timed out 1000 ms 111904 KB Execution timed out
68 Execution timed out 1000 ms 93244 KB Execution timed out
69 Memory limit exceeded 546 ms 131072 KB Memory limit exceeded
70 Execution timed out 1000 ms 79488 KB Execution timed out
71 Memory limit exceeded 539 ms 131072 KB Memory limit exceeded
72 Memory limit exceeded 513 ms 131072 KB Memory limit exceeded
73 Memory limit exceeded 566 ms 131072 KB Memory limit exceeded
74 Memory limit exceeded 526 ms 131072 KB Memory limit exceeded
75 Memory limit exceeded 553 ms 131072 KB Memory limit exceeded
76 Memory limit exceeded 553 ms 131072 KB Memory limit exceeded
77 Memory limit exceeded 629 ms 131072 KB Memory limit exceeded
78 Memory limit exceeded 616 ms 131072 KB Memory limit exceeded
79 Execution timed out 1000 ms 125244 KB Execution timed out
80 Execution timed out 1000 ms 125248 KB Execution timed out
81 Execution timed out 1000 ms 127116 KB Execution timed out
82 Execution timed out 1000 ms 89172 KB Execution timed out
83 Memory limit exceeded 619 ms 131072 KB Memory limit exceeded
84 Execution timed out 1000 ms 125228 KB Execution timed out
85 Memory limit exceeded 623 ms 131072 KB Memory limit exceeded
86 Execution timed out 1000 ms 111824 KB Execution timed out
87 Memory limit exceeded 549 ms 131072 KB Memory limit exceeded
88 Memory limit exceeded 559 ms 131072 KB Memory limit exceeded
89 Execution timed out 1000 ms 92616 KB Execution timed out
90 Execution timed out 1000 ms 83196 KB Execution timed out
91 Execution timed out 1000 ms 87044 KB Execution timed out
92 Execution timed out 1000 ms 95476 KB Execution timed out
93 Execution timed out 1000 ms 109320 KB Execution timed out
94 Execution timed out 1000 ms 90944 KB Execution timed out
95 Memory limit exceeded 546 ms 131072 KB Memory limit exceeded
96 Memory limit exceeded 576 ms 131072 KB Memory limit exceeded
97 Execution timed out 1000 ms 111524 KB Execution timed out
98 Execution timed out 1000 ms 89964 KB Execution timed out
99 Execution timed out 1000 ms 90408 KB Execution timed out
100 Execution timed out 1000 ms 108024 KB Execution timed out