oj.uz

Submission #842641

# Submission time Handle Problem Language Result Execution time Memory
842641 2023-09-03T06:52:36 Z nonono Soccer Stadium (IOI23_soccer) C++17
54 / 100
 239 ms 47404 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

void upMax(int &x, int y) {
    x = max(x, y);
}

int sub1(int N, vector<vector<int>> F) {
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            if(F[i][j] == 1) {
                return max({
                    N * i + N * j - i * j,
                    N * i + N * (N - j - 1) - i * (N - j - 1),
                    N * (N - i - 1) + N * j - (N - i - 1) * j,
                    N * (N - i - 1) + N * (N - j - 1) - (N - i - 1) * (N - j - 1) 
                });
            }
        }
    }
    
    return N * N;
}

int sub4(int N, vector<vector<int>> F) {
    for(int i = 0; i < N; i ++) {
        partial_sum(F[i].begin(), F[i].end(), F[i].begin());
    }
    
    auto get_sum = [&] (int row, int l, int r) {
        return F[row][r] - (!l ? 0 : F[row][l - 1]);
    };
    
    vector<vector<vector<vector<int>>>> dp(N, vector<vector<vector<int>>> (N, vector<vector<int>> (N, vector<int> (N, -1))));
    int result = 0;
    
    for(int first_row = N - 1; first_row >= 0; first_row --) {
        for(int last_row = first_row; last_row < N; last_row ++) {
            
            for(int l = 0; l < N; l ++) {
                for(int r = l; r < N; r ++) {
                    if(!get_sum(first_row, l, r)) {
                        dp[first_row][first_row][l][r] = r - l + 1;
                        upMax(result, dp[first_row][first_row][l][r]);
                    }
                }
            }
            
            for(int l = 0; l < N; l ++) {
                for(int r = l; r < N; r ++) {
                    
                    for(int _l = l; _l <= r; _l ++) {
                        for(int _r = _l; _r <= r; _r ++) {
                            
                            if(first_row + 1 < N && dp[first_row + 1][last_row][l][r] != -1 && !get_sum(first_row, _l, _r)) {
                                upMax(dp[first_row][last_row][_l][_r], dp[first_row + 1][last_row][l][r] + _r - _l + 1);
                            } 
                            
                            if(last_row - 1 >= 0 && dp[first_row][last_row - 1][l][r] != -1 && !get_sum(last_row, _l, _r)) {
                                upMax(dp[first_row][last_row][_l][_r], dp[first_row][last_row - 1][l][r] + _r - _l + 1);
                            }
                            
                            upMax(result, dp[first_row][last_row][_l][_r]);
                        }
                    }
                }
            }
        }
    }
    
    return result;
}

int biggest_stadium(int N, vector<vector<int>> F) {
    if(N <= 30) return sub4(N, F);
    return sub1(N, F);
}

/*int main() {
    int N;
    cin >> N;
    
    vector<vector<int>> F(N, vector<int> (N));
    
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            cin >> F[i][j];
        }
    }
    
    cout << biggest_stadium(N, F) << "\n";
    return 0;
}*/

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 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 15 ms 3224 KB ok
9 Correct 239 ms 47404 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 544 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 344 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 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 544 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 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 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 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 1 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 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 544 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 344 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 1 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 1 ms 348 KB ok
30 Correct 56 ms 4632 KB ok
31 Correct 58 ms 4444 KB ok
32 Correct 55 ms 4444 KB ok
33 Correct 56 ms 4444 KB ok
34 Correct 56 ms 4444 KB ok
35 Correct 56 ms 4608 KB ok
36 Correct 55 ms 4444 KB ok
37 Correct 55 ms 4440 KB ok
38 Correct 57 ms 4444 KB ok
39 Correct 66 ms 4608 KB ok
40 Correct 72 ms 4608 KB ok
41 Correct 64 ms 4444 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 544 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 344 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 1 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 1 ms 348 KB ok
30 Correct 56 ms 4632 KB ok
31 Correct 58 ms 4444 KB ok
32 Correct 55 ms 4444 KB ok
33 Correct 56 ms 4444 KB ok
34 Correct 56 ms 4444 KB ok
35 Correct 56 ms 4608 KB ok
36 Correct 55 ms 4444 KB ok
37 Correct 55 ms 4440 KB ok
38 Correct 57 ms 4444 KB ok
39 Correct 66 ms 4608 KB ok
40 Correct 72 ms 4608 KB ok
41 Correct 64 ms 4444 KB ok
42 Partially correct 20 ms 3160 KB partial
43 Partially correct 16 ms 3420 KB partial
44 Partially correct 15 ms 3228 KB partial
45 Partially correct 17 ms 3420 KB partial
46 Partially correct 16 ms 3420 KB partial
47 Partially correct 15 ms 3224 KB partial
48 Incorrect 17 ms 3224 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 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 15 ms 3224 KB ok
10 Correct 239 ms 47404 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 544 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 344 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 1 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 1 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 56 ms 4632 KB ok
36 Correct 58 ms 4444 KB ok
37 Correct 55 ms 4444 KB ok
38 Correct 56 ms 4444 KB ok
39 Correct 56 ms 4444 KB ok
40 Correct 56 ms 4608 KB ok
41 Correct 55 ms 4444 KB ok
42 Correct 55 ms 4440 KB ok
43 Correct 57 ms 4444 KB ok
44 Correct 66 ms 4608 KB ok
45 Correct 72 ms 4608 KB ok
46 Correct 64 ms 4444 KB ok
47 Partially correct 20 ms 3160 KB partial
48 Partially correct 16 ms 3420 KB partial
49 Partially correct 15 ms 3228 KB partial
50 Partially correct 17 ms 3420 KB partial
51 Partially correct 16 ms 3420 KB partial
52 Partially correct 15 ms 3224 KB partial
53 Incorrect 17 ms 3224 KB wrong
54 Halted 0 ms 0 KB -