oj.uz

Submission #1084803

# Submission time Handle Problem Language Result Execution time Memory
1084803 2024-09-07T03:20:54 Z thangdz2k7 Soccer Stadium (IOI23_soccer) C++17
100 / 100
 354 ms 55888 KB 
// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define left __left__
#define right __right__
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int MaxN = 2e5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int biggest_stadium(int n, vector <vi> f){
    vector <int> dp(n), h(n, -1);
    vector <vi> cur(n); int res = 0;
    for (int r = 0; r < n; ++ r){
        for (int c = 0; c < n; ++ c){
            if (f[r][c]){
                h[c] = -1;
                dp[c] = 0;
            }
            else cur[++ h[c]].pb(c);
        }

        vi left(n), right(n);
        stack <int> stk;
        for (int c = 0; c < n; ++ c){
            while (stk.size() && h[c] <= h[stk.top()]) stk.pop();
            left[c] = stk.empty() ? -1 : stk.top();
            stk.push(c);
        }
        while (stk.size()) stk.pop();
        for (int c = n - 1; c >= 0; -- c){
            while (stk.size() && h[c] <= h[stk.top()]) stk.pop();
            right[c] = stk.empty() ? n : stk.top();
            stk.push(c);
        }

        for (int hh = 0; hh < n; ++ hh){
            for (int c : cur[hh]){
                int len = right[c] - left[c] - 1;
                dp[c] += len;
                if (left[c] > -1) maxl(dp[c], dp[left[c]] + len * (h[c] - h[left[c]]));
                if (right[c] < n) maxl(dp[c], dp[right[c]] + len * (h[c] - h[right[c]]));
                maxl(res, dp[c]);
            }
            cur[hh].clear();
        }
    }

    return res;
}

Compilation message

soccer.cpp:20:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
soccer.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
soccer.cpp:21:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
soccer.cpp:21:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 17 ms 3720 KB ok
9 Correct 262 ms 55828 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 344 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 1 ms 344 KB ok
39 Correct 0 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 0 ms 348 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 344 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 1 ms 344 KB ok
39 Correct 0 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 0 ms 348 KB ok
42 Correct 23 ms 2904 KB ok
43 Correct 23 ms 2908 KB ok
44 Correct 19 ms 3208 KB ok
45 Correct 23 ms 3416 KB ok
46 Correct 22 ms 2908 KB ok
47 Correct 20 ms 3928 KB ok
48 Correct 17 ms 2948 KB ok
49 Correct 17 ms 2908 KB ok
50 Correct 20 ms 3420 KB ok
51 Correct 20 ms 2908 KB ok
52 Correct 16 ms 2908 KB ok
53 Correct 16 ms 2908 KB ok
54 Correct 17 ms 2908 KB ok
55 Correct 18 ms 2908 KB ok
56 Correct 16 ms 3160 KB ok
57 Correct 20 ms 3476 KB ok
58 Correct 18 ms 3416 KB ok
59 Correct 17 ms 3416 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 17 ms 3720 KB ok
10 Correct 262 ms 55828 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 344 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 348 KB ok
42 Correct 0 ms 348 KB ok
43 Correct 1 ms 344 KB ok
44 Correct 0 ms 348 KB ok
45 Correct 0 ms 348 KB ok
46 Correct 0 ms 348 KB ok
47 Correct 23 ms 2904 KB ok
48 Correct 23 ms 2908 KB ok
49 Correct 19 ms 3208 KB ok
50 Correct 23 ms 3416 KB ok
51 Correct 22 ms 2908 KB ok
52 Correct 20 ms 3928 KB ok
53 Correct 17 ms 2948 KB ok
54 Correct 17 ms 2908 KB ok
55 Correct 20 ms 3420 KB ok
56 Correct 20 ms 2908 KB ok
57 Correct 16 ms 2908 KB ok
58 Correct 16 ms 2908 KB ok
59 Correct 17 ms 2908 KB ok
60 Correct 18 ms 2908 KB ok
61 Correct 16 ms 3160 KB ok
62 Correct 20 ms 3476 KB ok
63 Correct 18 ms 3416 KB ok
64 Correct 17 ms 3416 KB ok
65 Correct 354 ms 35964 KB ok
66 Correct 313 ms 39796 KB ok
67 Correct 282 ms 39764 KB ok
68 Correct 303 ms 46140 KB ok
69 Correct 317 ms 40788 KB ok
70 Correct 346 ms 40020 KB ok
71 Correct 314 ms 52744 KB ok
72 Correct 304 ms 55688 KB ok
73 Correct 294 ms 39956 KB ok
74 Correct 290 ms 40276 KB ok
75 Correct 291 ms 40216 KB ok
76 Correct 262 ms 47696 KB ok
77 Correct 319 ms 47528 KB ok
78 Correct 328 ms 42324 KB ok
79 Correct 253 ms 39760 KB ok
80 Correct 267 ms 39764 KB ok
81 Correct 259 ms 39764 KB ok
82 Correct 277 ms 39760 KB ok
83 Correct 304 ms 39764 KB ok
84 Correct 262 ms 39700 KB ok
85 Correct 253 ms 39764 KB ok
86 Correct 258 ms 39828 KB ok
87 Correct 252 ms 40528 KB ok
88 Correct 266 ms 46868 KB ok
89 Correct 286 ms 55636 KB ok
90 Correct 285 ms 55888 KB ok
91 Correct 292 ms 47884 KB ok
92 Correct 270 ms 39764 KB ok
93 Correct 279 ms 39580 KB ok
94 Correct 257 ms 39760 KB ok
95 Correct 253 ms 39764 KB ok
96 Correct 245 ms 39700 KB ok
97 Correct 251 ms 39760 KB ok
98 Correct 246 ms 39760 KB ok
99 Correct 288 ms 40784 KB ok
100 Correct 286 ms 50328 KB ok
101 Correct 283 ms 51024 KB ok
102 Correct 280 ms 50204 KB ok
103 Correct 289 ms 49288 KB ok
104 Correct 278 ms 48724 KB ok
105 Correct 277 ms 48468 KB ok
106 Correct 283 ms 47956 KB ok
107 Correct 285 ms 47508 KB ok
108 Correct 283 ms 40276 KB ok
109 Correct 283 ms 41556 KB ok