oj.uz

Submission #843050

# Submission time Handle Problem Language Result Execution time Memory
843050 2023-09-03T15:19:38 Z nonono Soccer Stadium (IOI23_soccer) C++17
35.5 / 100
 1545 ms 584460 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN = 2000;

map<int, int> dp[mxN][mxN];

int full(int N, vector<vector<int>> F) {
    vector<vector<int>> sum(N, vector<int> (N, 0));
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            sum[i][j] = F[i][j];
            
            if(i) sum[i][j] += sum[i - 1][j];
            if(j) sum[i][j] += sum[i][j - 1];
            if(i && j) sum[i][j] -= sum[i - 1][j - 1]; 
            
        }
    }
    
    auto Area = [&] (int x, int y, int u, int v) {
        return sum[u][v] - (x ? sum[x - 1][v] : 0) - (y ? sum[u][y - 1] : 0) + (x && y ? sum[x - 1][y - 1] : 0);
    };
    
    auto Range = [&] (int x, int L, int R) {
        int low = x, high = x - 1;
        for(int i = 10; i >= 0; i --) {
            if(low - (1 << i) >= 0 && Area(low - (1 << i), L, x, R) == 0) low -= (1 << i);
            if(high + (1 << i) < N && Area(x, L, high + (1 << i), R) == 0) high += (1 << i);
        }
        
        return make_pair(low, high);
    };   
    
    function<int(int, int, int)> DP = [&] (int x, int L, int R) {
        if(dp[L][R].count(x)) return dp[L][R][x];
        auto [low, high] = Range(x, L, R);
        if(x != low) return DP(low, L, R);
        
        int ans = 0;
        for(int i = L; i <= R; i ++) {
            auto check = [&] (int r) {
                return low > 0 && Area(low - 1, i, low - 1, r) == 0;
            };
            
            if(check(i) == 0) continue ;
            
            int j = i;
            for(int k = 10; k >= 0; k --) if(j + (1 << k) < N && check(j + (1 << k))) j += (1 << k);
            auto [_low, _high] = Range(low - 1, i, j);
            ans = max(ans, DP(_low, i, j) + (low - _low + _high - high) * (j - i + 1));
            i = j;
        }
        
        for(int i = L; i <= R; i ++) {
            auto check = [&] (int r) {
                return high + 1 < N && Area(high + 1, i, high + 1, r) == 0;
            };
            
            if(check(i) == 0) continue ;
            
            int j = i;
            for(int k = 10; k >= 0; k --) if(j + (1 << k) < N && check(j + (1 << k))) j += (1 << k);
            auto [_low, _high] = Range(high + 1, i, j);
            ans = max(ans, DP(_low, i, j) + (low - _low + _high - high) * (j - i + 1));
            i = j;
        }
        
        return dp[L][R][x] = ans;
    };
    
    int result = 0;
    for(int i = 0; i < N; i ++) {
        pair<int, int> x = Range(i, 0, N - 1);
        result = max(result, DP(i, 0, N - 1) + (x.second - x.first + 1) * N);
    }
    
    return result;
}
 
int biggest_stadium(int N, vector<vector<int>> F) {
    return full(N, F);
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 188248 KB ok
2 Correct 39 ms 188240 KB ok
3 Correct 40 ms 188288 KB ok
4 Correct 36 ms 188176 KB ok
5 Correct 35 ms 188240 KB ok
6 Correct 38 ms 188240 KB ok
7 Correct 36 ms 188280 KB ok
8 Correct 53 ms 192080 KB ok
9 Correct 294 ms 251120 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 188248 KB ok
2 Correct 39 ms 188240 KB ok
3 Correct 36 ms 188244 KB ok
4 Correct 35 ms 188252 KB ok
5 Correct 36 ms 188244 KB ok
6 Correct 37 ms 188248 KB ok
7 Correct 36 ms 188244 KB ok
8 Correct 35 ms 188252 KB ok
9 Correct 37 ms 188164 KB ok
10 Correct 38 ms 188252 KB ok
11 Correct 37 ms 188252 KB ok
12 Correct 39 ms 188240 KB ok
13 Correct 39 ms 188252 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 188244 KB ok
2 Correct 35 ms 188248 KB ok
3 Correct 39 ms 188240 KB ok
4 Correct 36 ms 188244 KB ok
5 Correct 35 ms 188252 KB ok
6 Correct 36 ms 188244 KB ok
7 Correct 37 ms 188248 KB ok
8 Correct 36 ms 188244 KB ok
9 Correct 35 ms 188252 KB ok
10 Correct 37 ms 188164 KB ok
11 Correct 38 ms 188252 KB ok
12 Correct 37 ms 188252 KB ok
13 Correct 39 ms 188240 KB ok
14 Correct 39 ms 188252 KB ok
15 Correct 37 ms 188252 KB ok
16 Partially correct 37 ms 188244 KB partial
17 Partially correct 36 ms 188252 KB partial
18 Correct 36 ms 188252 KB ok
19 Correct 36 ms 188096 KB ok
20 Correct 35 ms 188080 KB ok
21 Correct 36 ms 188080 KB ok
22 Correct 39 ms 188024 KB ok
23 Correct 35 ms 188240 KB ok
24 Partially correct 37 ms 188248 KB partial
25 Correct 36 ms 188248 KB ok
26 Correct 36 ms 188252 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 188244 KB ok
2 Correct 35 ms 188248 KB ok
3 Correct 39 ms 188240 KB ok
4 Correct 40 ms 188288 KB ok
5 Correct 36 ms 188176 KB ok
6 Correct 36 ms 188244 KB ok
7 Correct 35 ms 188252 KB ok
8 Correct 36 ms 188244 KB ok
9 Correct 37 ms 188248 KB ok
10 Correct 36 ms 188244 KB ok
11 Correct 35 ms 188252 KB ok
12 Correct 37 ms 188164 KB ok
13 Correct 38 ms 188252 KB ok
14 Correct 37 ms 188252 KB ok
15 Correct 39 ms 188240 KB ok
16 Correct 39 ms 188252 KB ok
17 Correct 37 ms 188252 KB ok
18 Partially correct 37 ms 188244 KB partial
19 Partially correct 36 ms 188252 KB partial
20 Correct 36 ms 188252 KB ok
21 Correct 36 ms 188096 KB ok
22 Correct 35 ms 188080 KB ok
23 Correct 36 ms 188080 KB ok
24 Correct 39 ms 188024 KB ok
25 Correct 35 ms 188240 KB ok
26 Partially correct 37 ms 188248 KB partial
27 Correct 36 ms 188248 KB ok
28 Correct 36 ms 188252 KB ok
29 Correct 35 ms 188240 KB ok
30 Correct 38 ms 188248 KB ok
31 Correct 36 ms 188248 KB ok
32 Correct 35 ms 188252 KB ok
33 Correct 35 ms 188252 KB ok
34 Correct 35 ms 188252 KB ok
35 Correct 35 ms 188240 KB ok
36 Correct 36 ms 188252 KB ok
37 Partially correct 38 ms 188240 KB partial
38 Correct 35 ms 188248 KB ok
39 Correct 35 ms 188048 KB ok
40 Correct 35 ms 188276 KB ok
41 Correct 35 ms 188244 KB ok

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 188244 KB ok
2 Correct 35 ms 188248 KB ok
3 Correct 39 ms 188240 KB ok
4 Correct 40 ms 188288 KB ok
5 Correct 36 ms 188176 KB ok
6 Correct 36 ms 188244 KB ok
7 Correct 35 ms 188252 KB ok
8 Correct 36 ms 188244 KB ok
9 Correct 37 ms 188248 KB ok
10 Correct 36 ms 188244 KB ok
11 Correct 35 ms 188252 KB ok
12 Correct 37 ms 188164 KB ok
13 Correct 38 ms 188252 KB ok
14 Correct 37 ms 188252 KB ok
15 Correct 39 ms 188240 KB ok
16 Correct 39 ms 188252 KB ok
17 Correct 37 ms 188252 KB ok
18 Partially correct 37 ms 188244 KB partial
19 Partially correct 36 ms 188252 KB partial
20 Correct 36 ms 188252 KB ok
21 Correct 36 ms 188096 KB ok
22 Correct 35 ms 188080 KB ok
23 Correct 36 ms 188080 KB ok
24 Correct 39 ms 188024 KB ok
25 Correct 35 ms 188240 KB ok
26 Partially correct 37 ms 188248 KB partial
27 Correct 36 ms 188248 KB ok
28 Correct 36 ms 188252 KB ok
29 Correct 35 ms 188240 KB ok
30 Correct 38 ms 188248 KB ok
31 Correct 36 ms 188248 KB ok
32 Correct 35 ms 188252 KB ok
33 Correct 35 ms 188252 KB ok
34 Correct 35 ms 188252 KB ok
35 Correct 35 ms 188240 KB ok
36 Correct 36 ms 188252 KB ok
37 Partially correct 38 ms 188240 KB partial
38 Correct 35 ms 188248 KB ok
39 Correct 35 ms 188048 KB ok
40 Correct 35 ms 188276 KB ok
41 Correct 35 ms 188244 KB ok
42 Partially correct 88 ms 194672 KB partial
43 Partially correct 98 ms 195168 KB partial
44 Partially correct 63 ms 193104 KB partial
45 Partially correct 68 ms 192852 KB partial
46 Partially correct 76 ms 193812 KB partial
47 Partially correct 52 ms 192080 KB partial
48 Correct 61 ms 192188 KB ok
49 Partially correct 53 ms 192092 KB partial
50 Correct 66 ms 192088 KB ok
51 Partially correct 62 ms 193228 KB partial
52 Partially correct 54 ms 192304 KB partial
53 Partially correct 55 ms 192296 KB partial
54 Partially correct 56 ms 192152 KB partial
55 Partially correct 53 ms 192108 KB partial
56 Correct 52 ms 192180 KB ok
57 Correct 81 ms 208232 KB ok
58 Correct 90 ms 210004 KB ok
59 Correct 90 ms 212308 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 188244 KB ok
2 Correct 35 ms 188248 KB ok
3 Correct 39 ms 188240 KB ok
4 Correct 40 ms 188288 KB ok
5 Correct 36 ms 188176 KB ok
6 Correct 35 ms 188240 KB ok
7 Correct 38 ms 188240 KB ok
8 Correct 36 ms 188280 KB ok
9 Correct 53 ms 192080 KB ok
10 Correct 294 ms 251120 KB ok
11 Correct 36 ms 188244 KB ok
12 Correct 35 ms 188252 KB ok
13 Correct 36 ms 188244 KB ok
14 Correct 37 ms 188248 KB ok
15 Correct 36 ms 188244 KB ok
16 Correct 35 ms 188252 KB ok
17 Correct 37 ms 188164 KB ok
18 Correct 38 ms 188252 KB ok
19 Correct 37 ms 188252 KB ok
20 Correct 39 ms 188240 KB ok
21 Correct 39 ms 188252 KB ok
22 Correct 37 ms 188252 KB ok
23 Partially correct 37 ms 188244 KB partial
24 Partially correct 36 ms 188252 KB partial
25 Correct 36 ms 188252 KB ok
26 Correct 36 ms 188096 KB ok
27 Correct 35 ms 188080 KB ok
28 Correct 36 ms 188080 KB ok
29 Correct 39 ms 188024 KB ok
30 Correct 35 ms 188240 KB ok
31 Partially correct 37 ms 188248 KB partial
32 Correct 36 ms 188248 KB ok
33 Correct 36 ms 188252 KB ok
34 Correct 35 ms 188240 KB ok
35 Correct 38 ms 188248 KB ok
36 Correct 36 ms 188248 KB ok
37 Correct 35 ms 188252 KB ok
38 Correct 35 ms 188252 KB ok
39 Correct 35 ms 188252 KB ok
40 Correct 35 ms 188240 KB ok
41 Correct 36 ms 188252 KB ok
42 Partially correct 38 ms 188240 KB partial
43 Correct 35 ms 188248 KB ok
44 Correct 35 ms 188048 KB ok
45 Correct 35 ms 188276 KB ok
46 Correct 35 ms 188244 KB ok
47 Partially correct 88 ms 194672 KB partial
48 Partially correct 98 ms 195168 KB partial
49 Partially correct 63 ms 193104 KB partial
50 Partially correct 68 ms 192852 KB partial
51 Partially correct 76 ms 193812 KB partial
52 Partially correct 52 ms 192080 KB partial
53 Correct 61 ms 192188 KB ok
54 Partially correct 53 ms 192092 KB partial
55 Correct 66 ms 192088 KB ok
56 Partially correct 62 ms 193228 KB partial
57 Partially correct 54 ms 192304 KB partial
58 Partially correct 55 ms 192296 KB partial
59 Partially correct 56 ms 192152 KB partial
60 Partially correct 53 ms 192108 KB partial
61 Correct 52 ms 192180 KB ok
62 Correct 81 ms 208232 KB ok
63 Correct 90 ms 210004 KB ok
64 Correct 90 ms 212308 KB ok
65 Partially correct 1545 ms 289724 KB partial
66 Correct 1320 ms 286396 KB ok
67 Correct 640 ms 266760 KB ok
68 Partially correct 379 ms 254140 KB partial
69 Partially correct 596 ms 262632 KB partial
70 Partially correct 767 ms 269672 KB partial
71 Partially correct 328 ms 253168 KB partial
72 Partially correct 294 ms 251216 KB partial
73 Correct 309 ms 251256 KB ok
74 Correct 303 ms 251224 KB ok
75 Partially correct 299 ms 251220 KB partial
76 Correct 542 ms 251436 KB ok
77 Correct 544 ms 251312 KB ok
78 Partially correct 438 ms 259316 KB partial
79 Correct 403 ms 254464 KB ok
80 Partially correct 383 ms 253576 KB partial
81 Partially correct 372 ms 253516 KB partial
82 Partially correct 414 ms 256480 KB partial
83 Partially correct 718 ms 265300 KB partial
84 Partially correct 357 ms 251380 KB partial
85 Partially correct 325 ms 251296 KB partial
86 Partially correct 309 ms 251220 KB partial
87 Partially correct 343 ms 253008 KB partial
88 Correct 310 ms 251128 KB ok
89 Partially correct 297 ms 251220 KB partial
90 Partially correct 298 ms 251216 KB partial
91 Partially correct 301 ms 251140 KB partial
92 Correct 505 ms 260304 KB ok
93 Correct 567 ms 261680 KB ok
94 Correct 416 ms 254448 KB ok
95 Correct 354 ms 253016 KB ok
96 Correct 345 ms 252496 KB ok
97 Partially correct 336 ms 252148 KB partial
98 Correct 333 ms 251636 KB ok
99 Correct 1451 ms 300272 KB ok
100 Correct 1077 ms 502004 KB ok
101 Correct 933 ms 293992 KB ok
102 Correct 1018 ms 298564 KB ok
103 Correct 1129 ms 544896 KB ok
104 Correct 1147 ms 309576 KB ok
105 Correct 1220 ms 312000 KB ok
106 Correct 1274 ms 584460 KB ok
107 Correct 1281 ms 582028 KB ok
108 Partially correct 499 ms 255984 KB partial
109 Correct 524 ms 256016 KB ok