oj.uz

답안 #170283

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170283 2019-12-24T13:02:42 Z nvmdava Bomb (IZhO17_bomb) C++17
40 / 100
 376 ms 79788 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];
 
vector<pair<int, int> > v;

int ans[N][N], h[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    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';
        }
    }
    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]);
        }
    }

    memset(ans, 0x3f, sizeof ans);
    memset(h, 0x3f, sizeof h);

    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]){
                t += v.back().ss;
                v.pop_back();
                ans[max(up[i][j], v.back().ff) + 1][i] = min(ans[max(up[i][j], v.back().ff) + 1][i], t);
            }

            if(v.back().ff == up[i][j]){
                v.back().ss += 1 + t;
            } else {
                v.push_back({up[i][j], 1 + t});
            }
        }
    }
 
    int res = 0;
 
    for(int i = 1; i <= mx; ++i){
        for(int j = i; j <= n; j++){
            h[i] = min(h[i], ans[i][j]);
            ans[i + 1][j] = min(ans[i + 1][j], ans[i][j]);
        }
        res = max(res, h[i] * i); 
    }
    cout<<res;
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 24952 KB Output is correct
2 Correct 22 ms 25080 KB Output is correct
3 Correct 39 ms 45048 KB Output is correct
4 Correct 39 ms 45036 KB Output is correct
5 Correct 23 ms 24952 KB Output is correct
6 Correct 22 ms 24952 KB Output is correct
7 Correct 22 ms 24952 KB Output is correct
8 Correct 23 ms 25080 KB Output is correct
9 Incorrect 22 ms 25080 KB Output isn't correct
10 Correct 22 ms 25080 KB Output is correct
11 Correct 22 ms 25080 KB Output is correct
12 Correct 22 ms 25080 KB Output is correct
13 Correct 23 ms 25084 KB Output is correct
14 Correct 23 ms 25080 KB Output is correct
15 Correct 23 ms 25080 KB Output is correct
16 Correct 22 ms 25080 KB Output is correct
17 Incorrect 23 ms 25464 KB Output isn't correct
18 Correct 23 ms 25596 KB Output is correct
19 Correct 23 ms 25720 KB Output is correct
20 Incorrect 23 ms 25720 KB Output isn't correct
21 Correct 23 ms 25336 KB Output is correct
22 Correct 23 ms 25592 KB Output is correct
23 Incorrect 23 ms 25848 KB Output isn't correct
24 Incorrect 24 ms 25592 KB Output isn't correct
25 Incorrect 23 ms 25848 KB Output isn't correct
26 Incorrect 23 ms 25848 KB Output isn't correct
27 Correct 27 ms 28028 KB Output is correct
28 Correct 27 ms 28280 KB Output is correct
29 Incorrect 28 ms 29176 KB Output isn't correct
30 Incorrect 30 ms 30072 KB Output isn't correct
31 Incorrect 29 ms 28920 KB Output isn't correct
32 Incorrect 29 ms 29560 KB Output isn't correct
33 Incorrect 31 ms 30328 KB Output isn't correct
34 Correct 27 ms 28536 KB Output is correct
35 Incorrect 31 ms 30332 KB Output isn't correct
36 Incorrect 35 ms 30328 KB Output isn't correct
37 Incorrect 22 ms 25080 KB Output isn't correct
38 Correct 351 ms 78204 KB Output is correct
39 Incorrect 23 ms 25080 KB Output isn't correct
40 Incorrect 57 ms 38772 KB Output isn't correct
41 Incorrect 23 ms 25080 KB Output isn't correct
42 Incorrect 23 ms 25848 KB Output isn't correct
43 Correct 376 ms 78160 KB Output is correct
44 Incorrect 32 ms 30328 KB Output isn't correct
45 Incorrect 376 ms 78328 KB Output isn't correct
46 Correct 348 ms 78288 KB Output is correct
47 Incorrect 373 ms 78200 KB Output isn't correct
48 Incorrect 356 ms 78260 KB Output isn't correct
49 Correct 372 ms 78232 KB Output is correct
50 Incorrect 352 ms 78392 KB Output isn't correct
51 Incorrect 368 ms 78396 KB Output isn't correct
52 Incorrect 351 ms 78236 KB Output isn't correct
53 Incorrect 349 ms 78264 KB Output isn't correct
54 Correct 354 ms 78248 KB Output is correct
55 Correct 353 ms 78328 KB Output is correct
56 Correct 365 ms 78192 KB Output is correct
57 Correct 345 ms 78200 KB Output is correct
58 Correct 351 ms 78504 KB Output is correct
59 Correct 344 ms 78216 KB Output is correct
60 Correct 345 ms 78208 KB Output is correct
61 Correct 348 ms 78328 KB Output is correct
62 Correct 352 ms 78300 KB Output is correct
63 Correct 355 ms 78208 KB Output is correct
64 Correct 366 ms 78260 KB Output is correct
65 Incorrect 354 ms 78232 KB Output isn't correct
66 Incorrect 350 ms 78324 KB Output isn't correct
67 Incorrect 355 ms 78156 KB Output isn't correct
68 Incorrect 358 ms 78328 KB Output isn't correct
69 Correct 344 ms 78200 KB Output is correct
70 Incorrect 229 ms 67704 KB Output isn't correct
71 Incorrect 350 ms 78152 KB Output isn't correct
72 Incorrect 352 ms 78328 KB Output isn't correct
73 Incorrect 353 ms 78456 KB Output isn't correct
74 Incorrect 352 ms 78472 KB Output isn't correct
75 Incorrect 348 ms 78376 KB Output isn't correct
76 Incorrect 363 ms 78448 KB Output isn't correct
77 Incorrect 351 ms 79060 KB Output isn't correct
78 Incorrect 358 ms 79224 KB Output isn't correct
79 Incorrect 349 ms 79072 KB Output isn't correct
80 Incorrect 348 ms 79352 KB Output isn't correct
81 Incorrect 348 ms 79788 KB Output isn't correct
82 Incorrect 360 ms 79408 KB Output isn't correct
83 Incorrect 349 ms 79024 KB Output isn't correct
84 Incorrect 356 ms 78684 KB Output isn't correct
85 Incorrect 346 ms 78244 KB Output isn't correct
86 Correct 347 ms 78200 KB Output is correct
87 Correct 348 ms 77972 KB Output is correct
88 Incorrect 353 ms 77816 KB Output isn't correct
89 Incorrect 358 ms 77720 KB Output isn't correct
90 Incorrect 236 ms 66560 KB Output isn't correct
91 Incorrect 347 ms 77944 KB Output isn't correct
92 Incorrect 355 ms 78200 KB Output isn't correct
93 Incorrect 346 ms 77992 KB Output isn't correct
94 Incorrect 345 ms 77936 KB Output isn't correct
95 Incorrect 350 ms 78032 KB Output isn't correct
96 Incorrect 349 ms 78272 KB Output isn't correct
97 Incorrect 359 ms 78164 KB Output isn't correct
98 Incorrect 353 ms 78328 KB Output isn't correct
99 Incorrect 350 ms 78200 KB Output isn't correct
100 Incorrect 350 ms 78200 KB Output isn't correct