oj.uz

Submission #93311

# Submission time Handle Problem Language Result Execution time Memory
93311 2019-01-07T14:29:36 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 = 2600;

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 Incorrect 930 ms 67008 KB Output isn't correct
4 Correct 973 ms 67028 KB Output is correct
5 Correct 2 ms 376 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 764 KB Output is correct
15 Correct 2 ms 760 KB Output is correct
16 Incorrect 3 ms 888 KB Output isn't correct
17 Correct 20 ms 2168 KB Output is correct
18 Correct 19 ms 2168 KB Output is correct
19 Correct 43 ms 2680 KB Output is correct
20 Correct 44 ms 2680 KB Output is correct
21 Correct 16 ms 1528 KB Output is correct
22 Correct 32 ms 2168 KB Output is correct
23 Correct 65 ms 2808 KB Output is correct
24 Correct 30 ms 2424 KB Output is correct
25 Correct 65 ms 3192 KB Output is correct
26 Correct 65 ms 3296 KB Output is correct
27 Execution timed out 1076 ms 10028 KB Time limit exceeded
28 Execution timed out 1078 ms 7928 KB Time limit exceeded
29 Execution timed out 1050 ms 13432 KB Time limit exceeded
30 Execution timed out 1041 ms 14252 KB Time limit exceeded
31 Execution timed out 1071 ms 10872 KB Time limit exceeded
32 Execution timed out 1079 ms 13048 KB Time limit exceeded
33 Execution timed out 1084 ms 15736 KB Time limit exceeded
34 Execution timed out 1057 ms 8824 KB Time limit exceeded
35 Execution timed out 1065 ms 12536 KB Time limit exceeded
36 Execution timed out 1080 ms 17148 KB Time limit exceeded
37 Correct 3 ms 888 KB Output is correct
38 Runtime error 583 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Correct 2 ms 888 KB Output is correct
40 Execution timed out 1083 ms 42492 KB Time limit exceeded
41 Correct 3 ms 888 KB Output is correct
42 Correct 65 ms 3192 KB Output is correct
43 Runtime error 646 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Execution timed out 1074 ms 16632 KB Time limit exceeded
45 Runtime error 609 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Runtime error 552 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 640 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Runtime error 637 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Runtime error 620 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Runtime error 607 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Runtime error 612 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
52 Runtime error 601 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Runtime error 609 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Runtime error 739 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
55 Runtime error 759 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
56 Runtime error 567 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Runtime error 767 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
58 Runtime error 765 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
59 Runtime error 797 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Runtime error 690 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
61 Runtime error 617 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Runtime error 598 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 616 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
64 Runtime error 776 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Runtime error 595 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
66 Runtime error 655 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
67 Runtime error 605 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
68 Runtime error 599 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 826 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Execution timed out 1094 ms 100600 KB Time limit exceeded
71 Execution timed out 1085 ms 132096 KB Time limit exceeded
72 Runtime error 805 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 834 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 830 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 820 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 808 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 778 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 768 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Execution timed out 1068 ms 119804 KB Time limit exceeded
80 Execution timed out 1077 ms 121148 KB Time limit exceeded
81 Execution timed out 1083 ms 121612 KB Time limit exceeded
82 Runtime error 706 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 694 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Execution timed out 1077 ms 115416 KB Time limit exceeded
85 Runtime error 727 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 551 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 725 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 762 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 674 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Execution timed out 1082 ms 115080 KB Time limit exceeded
91 Runtime error 682 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 639 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
93 Runtime error 616 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
94 Runtime error 674 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
95 Runtime error 745 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
96 Runtime error 747 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
97 Runtime error 620 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
98 Runtime error 710 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
99 Runtime error 629 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
100 Runtime error 605 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)