oj.uz

Submission #366562

# Submission time Handle Problem Language Result Execution time Memory
366562 2021-02-14T14:08:45 Z nicolaalexandra Bomb (IZhO17_bomb) C++14
13 / 100
 1000 ms 131076 KB 
#include <bits/stdc++.h>
#define DIM 2502
using namespace std;

int n,m,i,j;
char s[DIM];
int dp_up[DIM][DIM],St[DIM],Dr[DIM],v[DIM][DIM],a[DIM][DIM];
deque <int> d;

struct event{
    int x,y,x2,y2,val;
};
vector <event> events;

inline int cmp (event a, event b){
    return a.val < b.val;
}

int verif (int poz){

    memset (v,0,sizeof v);
    int ok = 0;
    for (int i=poz;i<events.size();i++){
        int x = events[i].x, x2 = events[i].x2, y = events[i].y, y2 = events[i].y2;

        if (x <= 3 && 3 <= x2 && y <= 6 && 6 <= y2)
            ok = 1;

        v[x][y]++;
        v[x][y2+1]--;
        v[x2+1][y]--;
        v[x2+1][y2+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-1] - v[i-1][j-1];
            if (!v[i][j] && a[i][j])
                return 0;
        }

    return 1;
}

int main (){

    //ifstream cin ("bomb.in");
    //ofstream cout ("bomb.out");

    cin>>n>>m;
    for (i=1;i<=n;i++){
        cin>>s+1;
        for (j=1;j<=m;j++)
            a[i][j] = s[j] - '0';
    }

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (a[i][j])
                dp_up[i][j] = 1 + dp_up[i-1][j];

    for (i=1;i<=n;i++){
        memset (St,0,sizeof St);
        memset (Dr,0,sizeof Dr);
        d.clear();
        int last = 0;
        for (j=1;j<=m;j++){
            if (!dp_up[i][j]){
                d.clear();
                last = j;
            }

            while (!d.empty() && dp_up[i][j] <= dp_up[i][d.back()])
                d.pop_back();

            if (d.empty())
                St[j] = last;
            else St[j] = d.back();

            d.push_back(j);
        }


        d.clear(), last = m+1;

        for (j=m;j;j--){
            if (!dp_up[i][j]){
                d.clear();
                last = j;
            }

            while (!d.empty() && dp_up[i][j] <= dp_up[i][d.back()])
                d.pop_back();

            if (d.empty())
                Dr[j] = last;
            else Dr[j] = d.back();

            d.push_back(j);
        }

        for (j=1;j<=m;j++){
            if (!dp_up[i][j])
                continue;

            int x = i - dp_up[i][j] + 1, x2 = i;
            int y = St[j] + 1, y2 = Dr[j] - 1;

            if (x == 1 && x2 == 3 && y == 1 && y2 == 6)
                x = 1;

            events.push_back({x,y,x2,y2,dp_up[i][j] * (Dr[j] - St[j] - 1)});
        }
    }

    sort (events.begin(),events.end(),cmp);

    int st = 0, dr = events.size()-1, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid)){
            sol = events[mid].val;
            st = mid+1;
        } else dr = mid-1;
    }

    cout<<sol;

    return 0;
}

Compilation message

bomb.cpp: In function 'int verif(int)':
bomb.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i=poz;i<events.size();i++){
      |                    ~^~~~~~~~~~~~~~
bomb.cpp:22:9: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   22 |     int ok = 0;
      |         ^~
bomb.cpp: In function 'int main()':
bomb.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         cin>>s+1;
      |              ~^~

Subtask #1
13.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24812 KB Output is correct
2 Correct 20 ms 24940 KB Output is correct
3 Correct 60 ms 45036 KB Output is correct
4 Correct 59 ms 45100 KB Output is correct
5 Correct 49 ms 25088 KB Output is correct
6 Correct 43 ms 24940 KB Output is correct
7 Incorrect 26 ms 24960 KB Output isn't correct
8 Incorrect 30 ms 24960 KB Output isn't correct
9 Incorrect 33 ms 24940 KB Output isn't correct
10 Incorrect 30 ms 24940 KB Output isn't correct
11 Incorrect 30 ms 25068 KB Output isn't correct
12 Incorrect 26 ms 24940 KB Output isn't correct
13 Incorrect 30 ms 24960 KB Output isn't correct
14 Correct 33 ms 24940 KB Output is correct
15 Incorrect 33 ms 24940 KB Output isn't correct
16 Incorrect 36 ms 25196 KB Output isn't correct
17 Correct 46 ms 25452 KB Output is correct
18 Incorrect 34 ms 25324 KB Output isn't correct
19 Incorrect 44 ms 25580 KB Output isn't correct
20 Incorrect 44 ms 25600 KB Output isn't correct
21 Incorrect 33 ms 25196 KB Output isn't correct
22 Incorrect 38 ms 25452 KB Output isn't correct
23 Incorrect 46 ms 25708 KB Output isn't correct
24 Incorrect 43 ms 25472 KB Output isn't correct
25 Incorrect 50 ms 25836 KB Output isn't correct
26 Incorrect 57 ms 26024 KB Output isn't correct
27 Incorrect 89 ms 29672 KB Output isn't correct
28 Incorrect 47 ms 26732 KB Output isn't correct
29 Incorrect 100 ms 30940 KB Output isn't correct
30 Incorrect 86 ms 29792 KB Output isn't correct
31 Incorrect 71 ms 28516 KB Output isn't correct
32 Incorrect 75 ms 29156 KB Output isn't correct
33 Incorrect 91 ms 30816 KB Output isn't correct
34 Incorrect 50 ms 26988 KB Output isn't correct
35 Incorrect 68 ms 28220 KB Output isn't correct
36 Incorrect 125 ms 34516 KB Output isn't correct
37 Correct 36 ms 25196 KB Output is correct
38 Runtime error 293 ms 131076 KB Execution killed with signal 9
39 Correct 36 ms 25068 KB Output is correct
40 Incorrect 284 ms 53932 KB Output isn't correct
41 Correct 36 ms 25068 KB Output is correct
42 Correct 51 ms 25932 KB Output is correct
43 Runtime error 441 ms 131076 KB Execution killed with signal 9
44 Correct 114 ms 32496 KB Output is correct
45 Execution timed out 1063 ms 131076 KB Time limit exceeded
46 Runtime error 335 ms 131076 KB Execution killed with signal 9
47 Execution timed out 1099 ms 131072 KB Time limit exceeded
48 Runtime error 324 ms 131076 KB Execution killed with signal 9
49 Runtime error 297 ms 131076 KB Execution killed with signal 9
50 Runtime error 320 ms 131076 KB Execution killed with signal 9
51 Runtime error 322 ms 131076 KB Execution killed with signal 9
52 Runtime error 320 ms 131076 KB Execution killed with signal 9
53 Runtime error 324 ms 131076 KB Execution killed with signal 9
54 Incorrect 990 ms 110740 KB Output isn't correct
55 Execution timed out 1097 ms 107904 KB Time limit exceeded
56 Runtime error 300 ms 131076 KB Execution killed with signal 9
57 Execution timed out 1102 ms 103040 KB Time limit exceeded
58 Execution timed out 1087 ms 107904 KB Time limit exceeded
59 Execution timed out 1079 ms 104492 KB Time limit exceeded
60 Runtime error 860 ms 131076 KB Execution killed with signal 9
61 Runtime error 291 ms 131076 KB Execution killed with signal 9
62 Runtime error 290 ms 131076 KB Execution killed with signal 9
63 Runtime error 290 ms 131076 KB Execution killed with signal 9
64 Incorrect 937 ms 105768 KB Output isn't correct
65 Runtime error 833 ms 131076 KB Execution killed with signal 9
66 Runtime error 846 ms 131076 KB Execution killed with signal 9
67 Runtime error 314 ms 131076 KB Execution killed with signal 9
68 Runtime error 318 ms 131076 KB Execution killed with signal 9
69 Execution timed out 1104 ms 103424 KB Time limit exceeded
70 Incorrect 475 ms 61764 KB Output isn't correct
71 Incorrect 761 ms 86188 KB Output isn't correct
72 Incorrect 968 ms 99968 KB Output isn't correct
73 Execution timed out 1076 ms 103808 KB Time limit exceeded
74 Execution timed out 1066 ms 102400 KB Time limit exceeded
75 Execution timed out 1099 ms 105344 KB Time limit exceeded
76 Execution timed out 1101 ms 108032 KB Time limit exceeded
77 Execution timed out 1062 ms 110080 KB Time limit exceeded
78 Execution timed out 1074 ms 109312 KB Time limit exceeded
79 Incorrect 537 ms 58596 KB Output isn't correct
80 Incorrect 494 ms 59236 KB Output isn't correct
81 Incorrect 648 ms 63224 KB Output isn't correct
82 Execution timed out 1036 ms 113640 KB Time limit exceeded
83 Execution timed out 1100 ms 113408 KB Time limit exceeded
84 Incorrect 416 ms 56232 KB Output isn't correct
85 Execution timed out 1084 ms 108672 KB Time limit exceeded
86 Runtime error 378 ms 131076 KB Execution killed with signal 9
87 Execution timed out 1062 ms 105452 KB Time limit exceeded
88 Execution timed out 1073 ms 112640 KB Time limit exceeded
89 Execution timed out 1057 ms 131072 KB Time limit exceeded
90 Incorrect 612 ms 81068 KB Output isn't correct
91 Execution timed out 1065 ms 131072 KB Time limit exceeded
92 Execution timed out 1100 ms 131072 KB Time limit exceeded
93 Runtime error 377 ms 131076 KB Execution killed with signal 9
94 Execution timed out 1103 ms 131072 KB Time limit exceeded
95 Execution timed out 1097 ms 113688 KB Time limit exceeded
96 Execution timed out 1105 ms 113480 KB Time limit exceeded
97 Runtime error 377 ms 131076 KB Execution killed with signal 9
98 Execution timed out 1107 ms 113408 KB Time limit exceeded
99 Execution timed out 1060 ms 131072 KB Time limit exceeded
100 Runtime error 382 ms 131076 KB Execution killed with signal 9