oj.uz

답안 #847320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
847320 2023-09-09T13:29:21 Z Lucpp 축구 경기장 (IOI23_soccer) C++17
100 / 100
 565 ms 95060 KB 
#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;

int biggest_stadium(int N, vector<vector<int>> F){
    vector<vector<int>> L(N, vector<int>(N)), R(N, vector<int>(N, N)), H(N, vector<int>(N));
    vector<vector<int>> dp(N, vector<int>(N));
    int ans = 0;
    for(int i = 0; i < N; i++){
        if(i > 0) H[i] = H[i-1];
        for(int j = 0; j < N; j++){
            if(F[i][j]) H[i][j] = 0;
            else H[i][j]++;
        }
        stack<pair<int, int>> s;
        s.emplace(-1, -1);
        for(int k = 0; k < N; k++){
            while(s.top().first > H[i][k]){
                R[i][s.top().second] = k;
                s.pop();
            }
            if(s.top().first == H[i][k]) L[i][k] = L[i][s.top().second];
            else L[i][k] = s.top().second+1;
            s.emplace(H[i][k], k);
        }
        vector<int> ord(N);
        for(int j = 0; j < N; j++) ord[j] = j;
        sort(ord.begin(), ord.end(), [&](int a, int b){return H[i][a]<H[i][b];});
        for(int j : ord){
            if(H[i][j] == 0) continue;
            int w = R[i][j]-L[i][j];
            dp[i][j] = w*H[i][j];
            if(i > 0) dp[i][j] = max(dp[i][j], w+dp[i-1][j]);
            if(int k = L[i][j]-1; k >= 0){
                dp[i][j] = max(dp[i][j], w*(H[i][j]-H[i][k]) + dp[i][k]);
            }
            if(int k = R[i][j]; k < N){
                dp[i][j] = max(dp[i][j], w*(H[i][j]-H[i][k]) + dp[i][k]);
            }
            ans = max(ans, dp[i][j]);
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 1 ms 600 KB ok
8 Correct 21 ms 6288 KB ok
9 Correct 350 ms 94740 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 344 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 344 KB ok
17 Correct 1 ms 344 KB ok
18 Correct 0 ms 344 KB ok
19 Correct 0 ms 344 KB ok
20 Correct 1 ms 344 KB ok
21 Correct 0 ms 344 KB ok
22 Correct 0 ms 344 KB ok
23 Correct 0 ms 344 KB ok
24 Correct 0 ms 344 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 1 ms 348 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 1 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 344 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 0 ms 344 KB ok
19 Correct 1 ms 344 KB ok
20 Correct 0 ms 344 KB ok
21 Correct 0 ms 344 KB ok
22 Correct 1 ms 344 KB ok
23 Correct 0 ms 344 KB ok
24 Correct 0 ms 344 KB ok
25 Correct 0 ms 344 KB ok
26 Correct 0 ms 344 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 0 ms 344 KB ok
30 Correct 1 ms 344 KB ok
31 Correct 1 ms 344 KB ok
32 Correct 1 ms 344 KB ok
33 Correct 0 ms 344 KB ok
34 Correct 0 ms 344 KB ok
35 Correct 0 ms 344 KB ok
36 Correct 0 ms 344 KB ok
37 Correct 1 ms 344 KB ok
38 Correct 1 ms 344 KB ok
39 Correct 0 ms 344 KB ok
40 Correct 1 ms 344 KB ok
41 Correct 0 ms 344 KB ok

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 1 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 344 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 0 ms 344 KB ok
19 Correct 1 ms 344 KB ok
20 Correct 0 ms 344 KB ok
21 Correct 0 ms 344 KB ok
22 Correct 1 ms 344 KB ok
23 Correct 0 ms 344 KB ok
24 Correct 0 ms 344 KB ok
25 Correct 0 ms 344 KB ok
26 Correct 0 ms 344 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 0 ms 344 KB ok
30 Correct 1 ms 344 KB ok
31 Correct 1 ms 344 KB ok
32 Correct 1 ms 344 KB ok
33 Correct 0 ms 344 KB ok
34 Correct 0 ms 344 KB ok
35 Correct 0 ms 344 KB ok
36 Correct 0 ms 344 KB ok
37 Correct 1 ms 344 KB ok
38 Correct 1 ms 344 KB ok
39 Correct 0 ms 344 KB ok
40 Correct 1 ms 344 KB ok
41 Correct 0 ms 344 KB ok
42 Correct 31 ms 6232 KB ok
43 Correct 32 ms 6232 KB ok
44 Correct 32 ms 6232 KB ok
45 Correct 29 ms 6232 KB ok
46 Correct 32 ms 6232 KB ok
47 Correct 23 ms 6232 KB ok
48 Correct 23 ms 6232 KB ok
49 Correct 23 ms 6232 KB ok
50 Correct 22 ms 6224 KB ok
51 Correct 26 ms 6488 KB ok
52 Correct 24 ms 6292 KB ok
53 Correct 20 ms 6232 KB ok
54 Correct 20 ms 6232 KB ok
55 Correct 21 ms 6236 KB ok
56 Correct 25 ms 6232 KB ok
57 Correct 27 ms 6232 KB ok
58 Correct 28 ms 6232 KB ok
59 Correct 25 ms 6412 KB ok

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 1 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 1 ms 600 KB ok
9 Correct 21 ms 6288 KB ok
10 Correct 350 ms 94740 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 344 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 0 ms 344 KB ok
19 Correct 0 ms 344 KB ok
20 Correct 0 ms 344 KB ok
21 Correct 0 ms 344 KB ok
22 Correct 0 ms 344 KB ok
23 Correct 0 ms 344 KB ok
24 Correct 1 ms 344 KB ok
25 Correct 0 ms 344 KB ok
26 Correct 0 ms 344 KB ok
27 Correct 1 ms 344 KB ok
28 Correct 0 ms 344 KB ok
29 Correct 0 ms 344 KB ok
30 Correct 0 ms 344 KB ok
31 Correct 0 ms 344 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 0 ms 344 KB ok
35 Correct 1 ms 344 KB ok
36 Correct 1 ms 344 KB ok
37 Correct 1 ms 344 KB ok
38 Correct 0 ms 344 KB ok
39 Correct 0 ms 344 KB ok
40 Correct 0 ms 344 KB ok
41 Correct 0 ms 344 KB ok
42 Correct 1 ms 344 KB ok
43 Correct 1 ms 344 KB ok
44 Correct 0 ms 344 KB ok
45 Correct 1 ms 344 KB ok
46 Correct 0 ms 344 KB ok
47 Correct 31 ms 6232 KB ok
48 Correct 32 ms 6232 KB ok
49 Correct 32 ms 6232 KB ok
50 Correct 29 ms 6232 KB ok
51 Correct 32 ms 6232 KB ok
52 Correct 23 ms 6232 KB ok
53 Correct 23 ms 6232 KB ok
54 Correct 23 ms 6232 KB ok
55 Correct 22 ms 6224 KB ok
56 Correct 26 ms 6488 KB ok
57 Correct 24 ms 6292 KB ok
58 Correct 20 ms 6232 KB ok
59 Correct 20 ms 6232 KB ok
60 Correct 21 ms 6236 KB ok
61 Correct 25 ms 6232 KB ok
62 Correct 27 ms 6232 KB ok
63 Correct 28 ms 6232 KB ok
64 Correct 25 ms 6412 KB ok
65 Correct 510 ms 94808 KB ok
66 Correct 413 ms 94884 KB ok
67 Correct 354 ms 94780 KB ok
68 Correct 512 ms 95056 KB ok
69 Correct 565 ms 95060 KB ok
70 Correct 550 ms 94824 KB ok
71 Correct 463 ms 94752 KB ok
72 Correct 367 ms 94832 KB ok
73 Correct 380 ms 94800 KB ok
74 Correct 380 ms 94908 KB ok
75 Correct 374 ms 94800 KB ok
76 Correct 361 ms 94800 KB ok
77 Correct 365 ms 94740 KB ok
78 Correct 421 ms 94800 KB ok
79 Correct 341 ms 94740 KB ok
80 Correct 339 ms 94756 KB ok
81 Correct 346 ms 94800 KB ok
82 Correct 366 ms 94828 KB ok
83 Correct 371 ms 95056 KB ok
84 Correct 325 ms 95056 KB ok
85 Correct 329 ms 94744 KB ok
86 Correct 337 ms 94800 KB ok
87 Correct 333 ms 94800 KB ok
88 Correct 340 ms 94744 KB ok
89 Correct 381 ms 95056 KB ok
90 Correct 360 ms 94800 KB ok
91 Correct 373 ms 94800 KB ok
92 Correct 356 ms 95056 KB ok
93 Correct 354 ms 94832 KB ok
94 Correct 329 ms 94832 KB ok
95 Correct 358 ms 94800 KB ok
96 Correct 325 ms 95056 KB ok
97 Correct 323 ms 94740 KB ok
98 Correct 318 ms 94800 KB ok
99 Correct 412 ms 94804 KB ok
100 Correct 433 ms 94800 KB ok
101 Correct 411 ms 94800 KB ok
102 Correct 394 ms 94832 KB ok
103 Correct 401 ms 94736 KB ok
104 Correct 394 ms 94740 KB ok
105 Correct 396 ms 94800 KB ok
106 Correct 405 ms 94824 KB ok
107 Correct 403 ms 94800 KB ok
108 Correct 376 ms 94804 KB ok
109 Correct 385 ms 94800 KB ok