oj.uz

Submission #843048

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

const int mxN = 2000;

unordered_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 56 ms 219472 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 219472 KB ok
2 Correct 50 ms 219592 KB ok
3 Correct 50 ms 219472 KB ok
4 Correct 51 ms 219472 KB ok
5 Correct 51 ms 219472 KB ok
6 Correct 52 ms 219472 KB ok
7 Correct 52 ms 219728 KB ok
8 Correct 68 ms 223824 KB ok
9 Correct 337 ms 286900 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 219472 KB ok
2 Correct 50 ms 219592 KB ok
3 Correct 51 ms 219372 KB ok
4 Correct 50 ms 219472 KB ok
5 Correct 56 ms 219488 KB ok
6 Correct 51 ms 219476 KB ok
7 Correct 50 ms 219472 KB ok
8 Correct 50 ms 219472 KB ok
9 Correct 51 ms 219468 KB ok
10 Correct 51 ms 219480 KB ok
11 Correct 50 ms 219472 KB ok
12 Correct 50 ms 219472 KB ok
13 Correct 51 ms 219592 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 219472 KB ok
2 Correct 50 ms 219472 KB ok
3 Correct 50 ms 219592 KB ok
4 Correct 51 ms 219372 KB ok
5 Correct 50 ms 219472 KB ok
6 Correct 56 ms 219488 KB ok
7 Correct 51 ms 219476 KB ok
8 Correct 50 ms 219472 KB ok
9 Correct 50 ms 219472 KB ok
10 Correct 51 ms 219468 KB ok
11 Correct 51 ms 219480 KB ok
12 Correct 50 ms 219472 KB ok
13 Correct 50 ms 219472 KB ok
14 Correct 51 ms 219592 KB ok
15 Correct 50 ms 219472 KB ok
16 Partially correct 52 ms 219472 KB partial
17 Partially correct 50 ms 219612 KB partial
18 Correct 52 ms 219596 KB ok
19 Correct 50 ms 219472 KB ok
20 Correct 51 ms 219556 KB ok
21 Correct 55 ms 219588 KB ok
22 Correct 50 ms 219472 KB ok
23 Correct 49 ms 219480 KB ok
24 Partially correct 50 ms 219472 KB partial
25 Correct 50 ms 219596 KB ok
26 Correct 51 ms 219472 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 219472 KB ok
2 Correct 50 ms 219472 KB ok
3 Correct 50 ms 219592 KB ok
4 Correct 50 ms 219472 KB ok
5 Correct 51 ms 219472 KB ok
6 Correct 51 ms 219372 KB ok
7 Correct 50 ms 219472 KB ok
8 Correct 56 ms 219488 KB ok
9 Correct 51 ms 219476 KB ok
10 Correct 50 ms 219472 KB ok
11 Correct 50 ms 219472 KB ok
12 Correct 51 ms 219468 KB ok
13 Correct 51 ms 219480 KB ok
14 Correct 50 ms 219472 KB ok
15 Correct 50 ms 219472 KB ok
16 Correct 51 ms 219592 KB ok
17 Correct 50 ms 219472 KB ok
18 Partially correct 52 ms 219472 KB partial
19 Partially correct 50 ms 219612 KB partial
20 Correct 52 ms 219596 KB ok
21 Correct 50 ms 219472 KB ok
22 Correct 51 ms 219556 KB ok
23 Correct 55 ms 219588 KB ok
24 Correct 50 ms 219472 KB ok
25 Correct 49 ms 219480 KB ok
26 Partially correct 50 ms 219472 KB partial
27 Correct 50 ms 219596 KB ok
28 Correct 51 ms 219472 KB ok
29 Correct 49 ms 219472 KB ok
30 Correct 50 ms 219472 KB ok
31 Correct 50 ms 219472 KB ok
32 Correct 50 ms 219472 KB ok
33 Correct 50 ms 219472 KB ok
34 Correct 49 ms 219472 KB ok
35 Correct 50 ms 219472 KB ok
36 Correct 52 ms 220004 KB ok
37 Partially correct 50 ms 219472 KB partial
38 Correct 49 ms 219472 KB ok
39 Correct 50 ms 219472 KB ok
40 Correct 50 ms 219472 KB ok
41 Correct 51 ms 219472 KB ok

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 219472 KB ok
2 Correct 50 ms 219472 KB ok
3 Correct 50 ms 219592 KB ok
4 Correct 50 ms 219472 KB ok
5 Correct 51 ms 219472 KB ok
6 Correct 51 ms 219372 KB ok
7 Correct 50 ms 219472 KB ok
8 Correct 56 ms 219488 KB ok
9 Correct 51 ms 219476 KB ok
10 Correct 50 ms 219472 KB ok
11 Correct 50 ms 219472 KB ok
12 Correct 51 ms 219468 KB ok
13 Correct 51 ms 219480 KB ok
14 Correct 50 ms 219472 KB ok
15 Correct 50 ms 219472 KB ok
16 Correct 51 ms 219592 KB ok
17 Correct 50 ms 219472 KB ok
18 Partially correct 52 ms 219472 KB partial
19 Partially correct 50 ms 219612 KB partial
20 Correct 52 ms 219596 KB ok
21 Correct 50 ms 219472 KB ok
22 Correct 51 ms 219556 KB ok
23 Correct 55 ms 219588 KB ok
24 Correct 50 ms 219472 KB ok
25 Correct 49 ms 219480 KB ok
26 Partially correct 50 ms 219472 KB partial
27 Correct 50 ms 219596 KB ok
28 Correct 51 ms 219472 KB ok
29 Correct 49 ms 219472 KB ok
30 Correct 50 ms 219472 KB ok
31 Correct 50 ms 219472 KB ok
32 Correct 50 ms 219472 KB ok
33 Correct 50 ms 219472 KB ok
34 Correct 49 ms 219472 KB ok
35 Correct 50 ms 219472 KB ok
36 Correct 52 ms 220004 KB ok
37 Partially correct 50 ms 219472 KB partial
38 Correct 49 ms 219472 KB ok
39 Correct 50 ms 219472 KB ok
40 Correct 50 ms 219472 KB ok
41 Correct 51 ms 219472 KB ok
42 Partially correct 112 ms 226896 KB partial
43 Partially correct 123 ms 227024 KB partial
44 Partially correct 81 ms 225620 KB partial
45 Partially correct 77 ms 225176 KB partial
46 Partially correct 97 ms 226508 KB partial
47 Partially correct 78 ms 224080 KB partial
48 Correct 69 ms 224080 KB ok
49 Partially correct 69 ms 224080 KB partial
50 Correct 82 ms 224032 KB ok
51 Partially correct 80 ms 225104 KB partial
52 Partially correct 69 ms 224096 KB partial
53 Partially correct 73 ms 223900 KB partial
54 Partially correct 70 ms 224028 KB partial
55 Partially correct 68 ms 224084 KB partial
56 Correct 69 ms 224080 KB ok
57 Correct 103 ms 243796 KB ok
58 Correct 106 ms 246420 KB ok
59 Correct 112 ms 249168 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 219472 KB ok
2 Correct 50 ms 219472 KB ok
3 Correct 50 ms 219592 KB ok
4 Correct 50 ms 219472 KB ok
5 Correct 51 ms 219472 KB ok
6 Correct 51 ms 219472 KB ok
7 Correct 52 ms 219472 KB ok
8 Correct 52 ms 219728 KB ok
9 Correct 68 ms 223824 KB ok
10 Correct 337 ms 286900 KB ok
11 Correct 51 ms 219372 KB ok
12 Correct 50 ms 219472 KB ok
13 Correct 56 ms 219488 KB ok
14 Correct 51 ms 219476 KB ok
15 Correct 50 ms 219472 KB ok
16 Correct 50 ms 219472 KB ok
17 Correct 51 ms 219468 KB ok
18 Correct 51 ms 219480 KB ok
19 Correct 50 ms 219472 KB ok
20 Correct 50 ms 219472 KB ok
21 Correct 51 ms 219592 KB ok
22 Correct 50 ms 219472 KB ok
23 Partially correct 52 ms 219472 KB partial
24 Partially correct 50 ms 219612 KB partial
25 Correct 52 ms 219596 KB ok
26 Correct 50 ms 219472 KB ok
27 Correct 51 ms 219556 KB ok
28 Correct 55 ms 219588 KB ok
29 Correct 50 ms 219472 KB ok
30 Correct 49 ms 219480 KB ok
31 Partially correct 50 ms 219472 KB partial
32 Correct 50 ms 219596 KB ok
33 Correct 51 ms 219472 KB ok
34 Correct 49 ms 219472 KB ok
35 Correct 50 ms 219472 KB ok
36 Correct 50 ms 219472 KB ok
37 Correct 50 ms 219472 KB ok
38 Correct 50 ms 219472 KB ok
39 Correct 49 ms 219472 KB ok
40 Correct 50 ms 219472 KB ok
41 Correct 52 ms 220004 KB ok
42 Partially correct 50 ms 219472 KB partial
43 Correct 49 ms 219472 KB ok
44 Correct 50 ms 219472 KB ok
45 Correct 50 ms 219472 KB ok
46 Correct 51 ms 219472 KB ok
47 Partially correct 112 ms 226896 KB partial
48 Partially correct 123 ms 227024 KB partial
49 Partially correct 81 ms 225620 KB partial
50 Partially correct 77 ms 225176 KB partial
51 Partially correct 97 ms 226508 KB partial
52 Partially correct 78 ms 224080 KB partial
53 Correct 69 ms 224080 KB ok
54 Partially correct 69 ms 224080 KB partial
55 Correct 82 ms 224032 KB ok
56 Partially correct 80 ms 225104 KB partial
57 Partially correct 69 ms 224096 KB partial
58 Partially correct 73 ms 223900 KB partial
59 Partially correct 70 ms 224028 KB partial
60 Partially correct 68 ms 224084 KB partial
61 Correct 69 ms 224080 KB ok
62 Correct 103 ms 243796 KB ok
63 Correct 106 ms 246420 KB ok
64 Correct 112 ms 249168 KB ok
65 Partially correct 1563 ms 329196 KB partial
66 Correct 1234 ms 323072 KB ok
67 Correct 631 ms 305488 KB ok
68 Partially correct 398 ms 296352 KB partial
69 Partially correct 668 ms 310224 KB partial
70 Partially correct 841 ms 315984 KB partial
71 Partially correct 375 ms 294320 KB partial
72 Partially correct 331 ms 290384 KB partial
73 Correct 335 ms 290384 KB ok
74 Correct 358 ms 290556 KB ok
75 Partially correct 341 ms 290488 KB partial
76 Correct 593 ms 290552 KB ok
77 Correct 637 ms 290552 KB ok
78 Partially correct 457 ms 299856 KB partial
79 Correct 420 ms 294224 KB ok
80 Partially correct 404 ms 293812 KB partial
81 Partially correct 406 ms 295248 KB partial
82 Partially correct 486 ms 301016 KB partial
83 Partially correct 719 ms 304140 KB partial
84 Partially correct 337 ms 290604 KB partial
85 Partially correct 344 ms 290728 KB partial
86 Partially correct 339 ms 290736 KB partial
87 Partially correct 357 ms 293712 KB partial
88 Correct 339 ms 290348 KB ok
89 Partially correct 328 ms 290400 KB partial
90 Partially correct 339 ms 290608 KB partial
91 Partially correct 348 ms 290356 KB partial
92 Correct 579 ms 299304 KB ok
93 Correct 578 ms 300496 KB ok
94 Correct 420 ms 294996 KB ok
95 Correct 394 ms 293928 KB ok
96 Correct 374 ms 293200 KB ok
97 Partially correct 372 ms 292660 KB partial
98 Correct 354 ms 291372 KB ok
99 Correct 1187 ms 334868 KB ok
100 Correct 1106 ms 604204 KB ok
101 Correct 1043 ms 418116 KB ok
102 Correct 1102 ms 432208 KB ok
103 Correct 1261 ms 657304 KB ok
104 Correct 1343 ms 463556 KB ok
105 Correct 1339 ms 471216 KB ok
106 Correct 1398 ms 707012 KB ok
107 Correct 1394 ms 703724 KB ok
108 Partially correct 542 ms 296396 KB partial
109 Correct 598 ms 296652 KB ok