oj.uz

Submission #93321

# Submission time Handle Problem Language Result Execution time Memory
93321 2019-01-07T14:53:30 Z toloraia Bomb (IZhO17_bomb) C++14
26 / 100
 1000 ms 132096 KB 
#include <bits/stdc++.h>
#define ll long long
#pragma GCC ("O3")
#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;
}

Compilation message

bomb.cpp:3:0: warning: ignoring #pragma GCC  [-Wunknown-pragmas]
 #pragma GCC ("O3")

Subtask #1
26.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 892 KB Output is correct
3 Execution timed out 1024 ms 70972 KB Time limit exceeded
4 Execution timed out 1040 ms 70964 KB Time limit exceeded
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 3 ms 932 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 760 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Incorrect 3 ms 888 KB Output isn't correct
17 Correct 20 ms 2296 KB Output is correct
18 Correct 20 ms 2168 KB Output is correct
19 Correct 43 ms 2808 KB Output is correct
20 Correct 45 ms 2852 KB Output is correct
21 Correct 16 ms 1572 KB Output is correct
22 Correct 33 ms 2296 KB Output is correct
23 Correct 67 ms 3064 KB Output is correct
24 Correct 32 ms 2540 KB Output is correct
25 Correct 67 ms 3320 KB Output is correct
26 Correct 64 ms 3448 KB Output is correct
27 Execution timed out 1053 ms 10612 KB Time limit exceeded
28 Execution timed out 1070 ms 8440 KB Time limit exceeded
29 Execution timed out 1073 ms 14200 KB Time limit exceeded
30 Execution timed out 1076 ms 14968 KB Time limit exceeded
31 Execution timed out 1086 ms 11512 KB Time limit exceeded
32 Execution timed out 1069 ms 13816 KB Time limit exceeded
33 Execution timed out 1083 ms 16632 KB Time limit exceeded
34 Execution timed out 1074 ms 9396 KB Time limit exceeded
35 Execution timed out 1069 ms 13304 KB Time limit exceeded
36 Execution timed out 1050 ms 17992 KB Time limit exceeded
37 Correct 3 ms 888 KB Output is correct
38 Runtime error 346 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Correct 3 ms 888 KB Output is correct
40 Execution timed out 1078 ms 43904 KB Time limit exceeded
41 Correct 3 ms 888 KB Output is correct
42 Correct 68 ms 3480 KB Output is correct
43 Runtime error 512 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Execution timed out 1080 ms 17400 KB Time limit exceeded
45 Runtime error 528 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Runtime error 353 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 549 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Runtime error 392 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Runtime error 334 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Runtime error 403 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Runtime error 360 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
52 Runtime error 378 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Runtime error 359 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Runtime error 574 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
55 Runtime error 622 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
56 Runtime error 312 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Runtime error 670 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
58 Runtime error 704 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
59 Runtime error 674 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Runtime error 412 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
61 Runtime error 323 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Runtime error 344 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 319 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
64 Runtime error 528 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Runtime error 379 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
66 Runtime error 520 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
67 Runtime error 326 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
68 Runtime error 373 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 743 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Execution timed out 1088 ms 115448 KB Time limit exceeded
71 Runtime error 771 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Runtime error 749 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 716 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 740 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 740 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 730 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 729 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 725 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 982 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 964 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 971 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 690 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 693 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Execution timed out 1055 ms 132096 KB Time limit exceeded
85 Runtime error 659 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 395 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 742 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 720 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 625 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Execution timed out 1085 ms 129528 KB Time limit exceeded
91 Runtime error 668 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 594 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
93 Runtime error 386 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
94 Runtime error 585 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
95 Runtime error 632 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
96 Runtime error 699 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
97 Runtime error 403 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
98 Runtime error 697 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
99 Runtime error 626 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
100 Runtime error 424 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)