oj.uz

Submission #948473

# Submission time Handle Problem Language Result Execution time Memory
948473 2024-03-18T06:45:47 Z Trisanu_Das Soccer Stadium (IOI23_soccer) C++17
48 / 100
 18 ms 10840 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 30+5;
 
static int n;
static int arr[MAX_N][MAX_N];
 
static int pref_sum[MAX_N][MAX_N];
bool is_tree(int col, int i, int j) {
    return pref_sum[col][j] - pref_sum[col][i - 1];
}
static int dp[MAX_N][MAX_N][MAX_N][MAX_N];
static int seen[MAX_N][MAX_N][MAX_N][MAX_N];
int find_dp(int top, int bot, int l, int r) {
    if (r < l) return 0;
    if (top == 0 && bot == n + 1) return 0;
    if (seen[top][bot][l][r]) return dp[top][bot][l][r];
 
    dp[top][bot][l][r] = max(find_dp(top, bot, l + 1, r), find_dp(top, bot, l, r - 1));
    if (!is_tree(top, l, r) && top != 0) {
        int new_bot = (top == bot) ? bot + 1 : bot;
        dp[top][bot][l][r] = max(dp[top][bot][l][r], find_dp(top - 1, new_bot, l, r) + r - l + 1);
    }   
    if (!is_tree(bot, l, r) && bot != n + 1) {
        int new_top = (top == bot) ? top - 1 : top;
        dp[top][bot][l][r] = max(dp[top][bot][l][r], find_dp(new_top, bot + 1, l, r) + r - l + 1);
    }
    
    seen[top][bot][l][r] = true;
    //cout << top << " " << bot << " " << l << " " << r << " " << dp[top][bot][l][r] << '\n';
    return dp[top][bot][l][r];
}
 
int biggest_stadium(int xn, vector<vector<int>> xarr) {
    n = xn;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            arr[i + 1][j + 1] = xarr[i][j];
        }
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            pref_sum[i][j] = pref_sum[i][j - 1] + arr[i][j];
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, find_dp(i, i, 1, n));
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB ok
2 Correct 2 ms 4444 KB ok
3 Correct 1 ms 4700 KB ok
4 Correct 1 ms 4700 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 4444 KB ok
7 Runtime error 7 ms 10840 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 2 ms 4444 KB ok
4 Correct 1 ms 4700 KB ok
5 Correct 1 ms 4700 KB ok
6 Correct 1 ms 4440 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4444 KB ok
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4444 KB ok
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4444 KB ok
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4440 KB ok
17 Correct 1 ms 4696 KB ok
18 Correct 1 ms 4700 KB ok
19 Correct 1 ms 4700 KB ok
20 Correct 1 ms 4444 KB ok
21 Correct 1 ms 4444 KB ok
22 Correct 1 ms 4444 KB ok
23 Correct 1 ms 4700 KB ok
24 Correct 1 ms 4700 KB ok
25 Correct 1 ms 4444 KB ok
26 Correct 1 ms 4444 KB ok
27 Correct 1 ms 4444 KB ok
28 Correct 1 ms 4700 KB ok
29 Correct 1 ms 4444 KB ok
30 Correct 3 ms 9052 KB ok
31 Correct 2 ms 8540 KB ok
32 Correct 2 ms 7256 KB ok
33 Correct 2 ms 7004 KB ok
34 Correct 2 ms 8536 KB ok
35 Correct 2 ms 7516 KB ok
36 Correct 2 ms 7260 KB ok
37 Correct 2 ms 7260 KB ok
38 Correct 2 ms 7516 KB ok
39 Correct 2 ms 7772 KB ok
40 Correct 4 ms 8024 KB ok
41 Correct 5 ms 9048 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 2 ms 4444 KB ok
4 Correct 1 ms 4700 KB ok
5 Correct 1 ms 4700 KB ok
6 Correct 1 ms 4440 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4444 KB ok
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4444 KB ok
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4444 KB ok
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4440 KB ok
17 Correct 1 ms 4696 KB ok
18 Correct 1 ms 4700 KB ok
19 Correct 1 ms 4700 KB ok
20 Correct 1 ms 4444 KB ok
21 Correct 1 ms 4444 KB ok
22 Correct 1 ms 4444 KB ok
23 Correct 1 ms 4700 KB ok
24 Correct 1 ms 4700 KB ok
25 Correct 1 ms 4444 KB ok
26 Correct 1 ms 4444 KB ok
27 Correct 1 ms 4444 KB ok
28 Correct 1 ms 4700 KB ok
29 Correct 1 ms 4444 KB ok
30 Correct 3 ms 9052 KB ok
31 Correct 2 ms 8540 KB ok
32 Correct 2 ms 7256 KB ok
33 Correct 2 ms 7004 KB ok
34 Correct 2 ms 8536 KB ok
35 Correct 2 ms 7516 KB ok
36 Correct 2 ms 7260 KB ok
37 Correct 2 ms 7260 KB ok
38 Correct 2 ms 7516 KB ok
39 Correct 2 ms 7772 KB ok
40 Correct 4 ms 8024 KB ok
41 Correct 5 ms 9048 KB ok
42 Runtime error 18 ms 4952 KB Execution killed with signal 11
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 2 ms 4444 KB ok
4 Correct 1 ms 4700 KB ok
5 Correct 1 ms 4700 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 4444 KB ok
8 Runtime error 7 ms 10840 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -