oj.uz

답안 #170264

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170264 2019-12-24T12:25:52 Z nvmdava Bomb (IZhO17_bomb) C++17
38 / 100
 384 ms 78492 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define N 2505
 
int a[N][N];
int up[N][N], le[N][N];
 
int h[2505], w[2505];
 
vector<pair<int, int> > v;
int pre[N][N];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(h, 0x3f, sizeof h);
    memset(w, 0x3f, sizeof w);
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            char c;
            cin>>c;
            a[i][j] = c - '0';
            pre[i][j] = pre[i][j - 1] + a[i][j];
        }
    }
    int mx=  2500;
    for(int i = 1; i <= m; ++i){
        for(int j = 1; j <= n; ++j){
            if(a[j][i] == 0) up[j][i] = 0;
            else up[j][i] = up[j - 1][i] + 1;
            if(a[j + 1][i] == 0 && a[j][i] == 1)mx = min(mx, up[j][i]);
        }
    }
    v.push_back({0, 0});
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m + 1; ++j){
            int t = 0;
            while(v.back().ff > up[i][j]){
                v.back().ss += t;
                t = v.back().ss;
                v.pop_back();
                if(pre[i + 1][j - 1] - pre[i + 1][j - 1 - t] != t)
                   h[max(up[i][j], v.back().ff) + 1] = min(h[max(up[i][j], v.back().ff) + 1], t);
            }
            if(v.back().ff == up[i][j]){
                v.back().ss += 1 + t;
            } else {
                v.push_back({up[i][j], 1 + t});
            }
        }
    }
 
    int ans = 0;
 
    for(int i = 1; i <= mx; ++i){
        h[i] = min(h[i - 1], h[i]);
        ans = max(ans, h[i] * i);
    }
    cout<<ans;
}

Subtask #1
38.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 29 ms 30584 KB Output is correct
4 Correct 29 ms 30456 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 2 ms 504 KB Output isn't correct
8 Incorrect 2 ms 632 KB Output isn't correct
9 Incorrect 2 ms 632 KB Output isn't correct
10 Incorrect 2 ms 504 KB Output isn't correct
11 Correct 2 ms 632 KB Output is correct
12 Incorrect 2 ms 504 KB Output isn't correct
13 Incorrect 2 ms 504 KB Output isn't correct
14 Correct 2 ms 504 KB Output is correct
15 Incorrect 2 ms 632 KB Output isn't correct
16 Incorrect 2 ms 632 KB Output isn't correct
17 Correct 3 ms 1272 KB Output is correct
18 Incorrect 3 ms 1272 KB Output isn't correct
19 Incorrect 3 ms 1656 KB Output isn't correct
20 Incorrect 3 ms 1656 KB Output isn't correct
21 Incorrect 3 ms 1144 KB Output isn't correct
22 Incorrect 3 ms 1400 KB Output isn't correct
23 Incorrect 3 ms 1656 KB Output isn't correct
24 Incorrect 3 ms 1528 KB Output isn't correct
25 Incorrect 3 ms 1784 KB Output isn't correct
26 Incorrect 3 ms 1656 KB Output isn't correct
27 Incorrect 8 ms 4956 KB Output isn't correct
28 Incorrect 9 ms 5240 KB Output isn't correct
29 Incorrect 11 ms 6652 KB Output isn't correct
30 Incorrect 16 ms 7928 KB Output isn't correct
31 Correct 10 ms 6336 KB Output is correct
32 Incorrect 12 ms 7288 KB Output isn't correct
33 Incorrect 13 ms 8312 KB Output isn't correct
34 Incorrect 8 ms 5752 KB Output isn't correct
35 Incorrect 13 ms 8440 KB Output isn't correct
36 Incorrect 14 ms 8440 KB Output isn't correct
37 Correct 2 ms 632 KB Output is correct
38 Correct 354 ms 78300 KB Output is correct
39 Correct 3 ms 760 KB Output is correct
40 Correct 49 ms 20728 KB Output is correct
41 Correct 2 ms 632 KB Output is correct
42 Correct 4 ms 1656 KB Output is correct
43 Correct 375 ms 78328 KB Output is correct
44 Correct 14 ms 8312 KB Output is correct
45 Correct 369 ms 78328 KB Output is correct
46 Correct 357 ms 78296 KB Output is correct
47 Correct 374 ms 78212 KB Output is correct
48 Correct 355 ms 78456 KB Output is correct
49 Incorrect 373 ms 78328 KB Output isn't correct
50 Correct 356 ms 78348 KB Output is correct
51 Correct 355 ms 78328 KB Output is correct
52 Correct 357 ms 78200 KB Output is correct
53 Correct 370 ms 78328 KB Output is correct
54 Incorrect 350 ms 78172 KB Output isn't correct
55 Incorrect 349 ms 78492 KB Output isn't correct
56 Correct 354 ms 78328 KB Output is correct
57 Incorrect 361 ms 78328 KB Output isn't correct
58 Incorrect 347 ms 78276 KB Output isn't correct
59 Incorrect 353 ms 78200 KB Output isn't correct
60 Correct 355 ms 78328 KB Output is correct
61 Incorrect 369 ms 78200 KB Output isn't correct
62 Incorrect 360 ms 78328 KB Output isn't correct
63 Incorrect 366 ms 78272 KB Output isn't correct
64 Correct 346 ms 78328 KB Output is correct
65 Correct 356 ms 78284 KB Output is correct
66 Correct 348 ms 78200 KB Output is correct
67 Correct 362 ms 78456 KB Output is correct
68 Correct 359 ms 78296 KB Output is correct
69 Incorrect 384 ms 78248 KB Output isn't correct
70 Incorrect 230 ms 62328 KB Output isn't correct
71 Incorrect 347 ms 78408 KB Output isn't correct
72 Incorrect 348 ms 78200 KB Output isn't correct
73 Correct 347 ms 78072 KB Output is correct
74 Incorrect 349 ms 78072 KB Output isn't correct
75 Incorrect 356 ms 78228 KB Output isn't correct
76 Incorrect 365 ms 78268 KB Output isn't correct
77 Incorrect 349 ms 77468 KB Output isn't correct
78 Incorrect 354 ms 76792 KB Output isn't correct
79 Incorrect 354 ms 76664 KB Output isn't correct
80 Incorrect 348 ms 76732 KB Output isn't correct
81 Incorrect 350 ms 77212 KB Output isn't correct
82 Incorrect 348 ms 76976 KB Output isn't correct
83 Incorrect 349 ms 77508 KB Output isn't correct
84 Incorrect 347 ms 77688 KB Output isn't correct
85 Incorrect 368 ms 77084 KB Output isn't correct
86 Incorrect 375 ms 77868 KB Output isn't correct
87 Incorrect 353 ms 77888 KB Output isn't correct
88 Correct 351 ms 77960 KB Output is correct
89 Correct 351 ms 77500 KB Output is correct
90 Incorrect 230 ms 62788 KB Output isn't correct
91 Incorrect 349 ms 77552 KB Output isn't correct
92 Incorrect 348 ms 77756 KB Output isn't correct
93 Incorrect 349 ms 77492 KB Output isn't correct
94 Correct 349 ms 77224 KB Output is correct
95 Incorrect 345 ms 77304 KB Output isn't correct
96 Correct 357 ms 77300 KB Output is correct
97 Incorrect 359 ms 77488 KB Output isn't correct
98 Incorrect 351 ms 77508 KB Output isn't correct
99 Incorrect 347 ms 77304 KB Output isn't correct
100 Incorrect 353 ms 77248 KB Output isn't correct