oj.uz

Submission #93314

# Submission time Handle Problem Language Result Execution time Memory
93314 2019-01-07T14:37:16 Z toloraia Bomb (IZhO17_bomb) C++14
27 / 100
 1000 ms 132096 KB 
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
 
const int N = 5100;
 
int n, m;
char ch[N][N];
int a[N][N], b[N][N];
int c[N][N], d[N][N];
int A[N][N], B[N][N];
 
deque < pair < int, int > > Q;
 
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin>>ch[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (ch[i][j] == '1')
                a[i][j] = a[i][j - 1] + 1;
    for (int i = n; i >= 1; i--)
        for (int j = m; j >= 1; j--)
            if (ch[i][j] == '1')
                b[i][j] = b[i][j + 1] + 1;
    int ans = 1;
    for (int I = 1; I <= n; I++){
        for (int j = 1; j <= m; j++){
            while ((int)Q.size() > 0)
                Q.pop_back();
            for (int i = 1; i <= n; i++){
                while ((int)Q.size() > 0 && Q.back().F >= a[i][j])
                    Q.pop_back();
                Q.push_back ({a[i][j], i});
                while (Q.front().S <= i - I)
                    Q.pop_front();
                c[max (1, i - I + 1)][j] = Q.front().F;
            }
 
 
 
            while ((int)Q.size() > 0)
                Q.pop_back();
            for (int i = 1; i <= n; i++){
                while ((int)Q.size() > 0 && Q.back().F >= b[i][j])
                    Q.pop_back();
                Q.push_back ({b[i][j], i});
                while (Q.front().S <= i - I)
                    Q.pop_front();
                d[max (1, i - I + 1)][j] = Q.front().F;
            }
 
 
 
            while ((int)Q.size() > 0)
                Q.pop_back();
            for (int i = 1; i <= n; i++){
                while ((int)Q.size() > 0 && Q.back().F <= c[i][j])
                    Q.pop_back();
                Q.push_back ({c[i][j], i});
                while (Q.front().S <= i - I)
                    Q.pop_front();
                A[i][j] = Q.front().F;
            }
 
 
 
            while ((int)Q.size() > 0)
                Q.pop_back();
            for (int i = 1; i <= n; i++){
                while ((int)Q.size() > 0 && Q.back().F <= d[i][j])
                    Q.pop_back();
                Q.push_back ({d[i][j], i});
                while (Q.front().S <= i - I)
                    Q.pop_front();
                B[i][j] = Q.front().F;
            }
        }
        int J = m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (ch[i][j] == '1')
                    J = min (J, A[i][j] + B[i][j] - 1);
        ans = max (ans, I * J);
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
27.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Execution timed out 1041 ms 70904 KB Time limit exceeded
4 Correct 978 ms 71032 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 888 KB Output is correct
9 Correct 2 ms 888 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Incorrect 2 ms 760 KB Output isn't correct
14 Correct 2 ms 888 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Incorrect 3 ms 1016 KB Output isn't correct
17 Correct 20 ms 2296 KB Output is correct
18 Correct 19 ms 2168 KB Output is correct
19 Correct 44 ms 2808 KB Output is correct
20 Correct 47 ms 2936 KB Output is correct
21 Correct 17 ms 1656 KB Output is correct
22 Correct 33 ms 2296 KB Output is correct
23 Correct 67 ms 3128 KB Output is correct
24 Correct 32 ms 2552 KB Output is correct
25 Correct 64 ms 3324 KB Output is correct
26 Correct 66 ms 3448 KB Output is correct
27 Execution timed out 1080 ms 10640 KB Time limit exceeded
28 Execution timed out 1071 ms 8440 KB Time limit exceeded
29 Execution timed out 1080 ms 14200 KB Time limit exceeded
30 Execution timed out 1083 ms 14968 KB Time limit exceeded
31 Execution timed out 1090 ms 11516 KB Time limit exceeded
32 Execution timed out 1081 ms 13816 KB Time limit exceeded
33 Execution timed out 1082 ms 16504 KB Time limit exceeded
34 Execution timed out 1078 ms 9464 KB Time limit exceeded
35 Execution timed out 1087 ms 13304 KB Time limit exceeded
36 Execution timed out 1088 ms 17940 KB Time limit exceeded
37 Correct 3 ms 1016 KB Output is correct
38 Runtime error 348 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Correct 3 ms 1016 KB Output is correct
40 Execution timed out 1094 ms 43900 KB Time limit exceeded
41 Correct 2 ms 888 KB Output is correct
42 Correct 66 ms 3440 KB Output is correct
43 Runtime error 494 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Execution timed out 1081 ms 17400 KB Time limit exceeded
45 Runtime error 539 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Runtime error 351 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 545 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Runtime error 398 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Runtime error 350 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Runtime error 400 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Runtime error 374 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
52 Runtime error 383 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Runtime error 371 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Runtime error 654 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
55 Runtime error 662 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
56 Runtime error 322 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Runtime error 753 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
58 Runtime error 689 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
59 Runtime error 689 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Runtime error 419 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
61 Runtime error 362 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Runtime error 327 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 322 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
64 Runtime error 543 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Runtime error 365 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
66 Runtime error 566 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
67 Runtime error 351 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
68 Runtime error 356 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 689 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Execution timed out 1088 ms 115408 KB Time limit exceeded
71 Runtime error 815 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Runtime error 768 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 761 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 754 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 738 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 698 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 705 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 735 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 951 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 970 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 976 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 705 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 644 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 951 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 719 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 398 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 727 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 701 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 588 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Execution timed out 1084 ms 129340 KB Time limit exceeded
91 Runtime error 686 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 604 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
93 Runtime error 420 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
94 Runtime error 636 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
95 Runtime error 716 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
96 Runtime error 692 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
97 Runtime error 407 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
98 Runtime error 722 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
99 Runtime error 588 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
100 Runtime error 442 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)