oj.uz

Submission #38411

# Submission time Handle Problem Language Result Execution time Memory
38411 2018-01-04T05:21:52 Z Talant Bomb (IZhO17_bomb) C++14
15 / 100
 209 ms 131072 KB 
#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const int inf = (int)1e9 + 7;
const int N = (int)1e6 + 10;

int n,m;
char a[2501][2501];
int t[2501][2501];
int c[2501][2501];
int mx,mn = inf,mn1 = inf;
vector <pair<int,int> > v;

bool check (int h,int w) {
        for (int l = 0; l < v.size(); l ++) {
                int f = 0;
                for (int i = v[l].fr; i <= min(n,v[l].fr + h - 1); i ++) {
                        for (int j = v[l].sc; j <= min(m,v[l].sc + w - 1); j ++) {
                                if (c[i][j] - c[i - h][j] - c[i][j - w] + c[i - h][j - w] == (h * w)) {
                                        f = 1;
                                        break;
                                }
                        }
                        if (f == 1)
                                break;
                }
                if (!f)
                        return false;
        }
        return true;
}
int main () {
        cin >> n >> m;

        for (int i = 1; i <= n; i ++)
                scanf ("%s", a[i] + 1);

        for (int i = 1; i <= n; i ++) {
                int cnt = 0;
                for (int j = 1; j <= m; j ++) {
                        t[i][j] = int(a[i][j] - '0');
                        c[i][j] = t[i][j];
                        if (t[i][j] == 1)
                                v.pb(mk(i,j));
                        if (c[i][j] == 1)
                                cnt ++;
                        else {
                                if (cnt > 0)
                                mn = min(mn,cnt);
                        cnt = 0;
                        }
                }
                if (cnt > 0)
                        mn = min(mn,cnt);
        }
        for (int i = 1; i <= m; i ++) {
                int cnt = 0;
                for (int j = 1; j <= n; j ++) {
                        if (c[j][i] == 1)
                                cnt ++;
                        else {
                                if (cnt > 0)
                                mn1 = min(mn1,cnt);
                        cnt = 0;
                        }
                }
                if (cnt > 0)
                        mn1 = min(mn1,cnt);
        }
        if (mn == inf)
                mn = 0;
        if (mn1 == inf)
                mn1 = 0;

        if (mn * mn1 == 0) {
                cout << 0;
                return 0;
        }

        if (check(mn1,mn)) {
                cout << mn1 * mn;
                return 0;
        }

        for (int i = 1; i <= n; i ++)
                for (int j = 2; j <= m; j ++)
                        c[i][j] += c[i][j - 1];

        for (int i = 2; i <= n; i ++)
                for (int j = 1; j <= m; j ++)
                        c[i][j] += c[i - 1][j];

        for (int i = 1; i <= mn1; i ++) {
                for (int j = 1; j <= mn; j ++) {
                         if (mx >= i * j)
                                continue;
                         if (check(i,j))
                                mx = max(mx,i * j);
                }
        }
        cout << mx << endl;
}

Compilation message

bomb.cpp: In function 'bool check(int, int)':
bomb.cpp:24:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int l = 0; l < v.size(); l ++) {
                           ^
bomb.cpp: In function 'int main()':
bomb.cpp:45:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%s", a[i] + 1);
                                       ^

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 56992 KB Output is correct
2 Correct 0 ms 56992 KB Output is correct
3 Runtime error 0 ms 57132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 57132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 0 ms 57132 KB Output is correct
6 Correct 0 ms 56992 KB Output is correct
7 Correct 0 ms 56992 KB Output is correct
8 Correct 0 ms 56992 KB Output is correct
9 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 0 ms 56992 KB Output is correct
11 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 0 ms 56992 KB Output is correct
13 Correct 0 ms 56992 KB Output is correct
14 Correct 0 ms 56992 KB Output is correct
15 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Correct 0 ms 56992 KB Output is correct
17 Correct 0 ms 56992 KB Output is correct
18 Correct 0 ms 56992 KB Output is correct
19 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Correct 0 ms 56992 KB Output is correct
22 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 0 ms 57132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 0 ms 57132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 0 ms 57264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Correct 0 ms 58612 KB Output is correct
28 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 3 ms 58612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 3 ms 57844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 0 ms 57460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 6 ms 57460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 6 ms 57844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 6 ms 57264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 3 ms 60148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Memory limit exceeded 86 ms 131072 KB Memory limit exceeded
39 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 19 ms 69364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 0 ms 56992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 0 ms 57132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Memory limit exceeded 86 ms 131072 KB Memory limit exceeded
44 Runtime error 6 ms 58612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 209 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 159 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 176 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 196 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Memory limit exceeded 106 ms 131072 KB Memory limit exceeded
50 Runtime error 159 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 186 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 153 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 173 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 143 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 156 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Memory limit exceeded 89 ms 131072 KB Memory limit exceeded
57 Runtime error 123 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
58 Runtime error 183 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 149 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Runtime error 153 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Memory limit exceeded 89 ms 131072 KB Memory limit exceeded
62 Memory limit exceeded 86 ms 131072 KB Memory limit exceeded
63 Memory limit exceeded 96 ms 131072 KB Memory limit exceeded
64 Runtime error 186 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 196 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 196 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 203 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Memory limit exceeded 109 ms 131072 KB Memory limit exceeded
69 Runtime error 146 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
70 Runtime error 96 ms 63220 KB Execution killed with signal 11 (could be triggered by violating memory limits)
71 Runtime error 136 ms 69364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
72 Runtime error 189 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Runtime error 163 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
74 Runtime error 126 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
75 Runtime error 153 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
76 Runtime error 159 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Runtime error 146 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
78 Runtime error 153 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
79 Runtime error 116 ms 57460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
80 Runtime error 146 ms 57460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
81 Runtime error 113 ms 60148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
82 Runtime error 136 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
83 Runtime error 173 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
84 Runtime error 133 ms 57264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
85 Runtime error 156 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
86 Memory limit exceeded 83 ms 131072 KB Memory limit exceeded
87 Runtime error 139 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
88 Runtime error 183 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
89 Runtime error 146 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
90 Runtime error 79 ms 69364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
91 Runtime error 133 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
92 Runtime error 189 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
93 Memory limit exceeded 89 ms 131072 KB Memory limit exceeded
94 Runtime error 153 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
95 Runtime error 166 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
96 Runtime error 146 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
97 Memory limit exceeded 79 ms 131072 KB Memory limit exceeded
98 Runtime error 189 ms 81652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
99 Runtime error 176 ms 106228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
100 Memory limit exceeded 89 ms 131072 KB Memory limit exceeded