oj.uz

Submission #1070725

# Submission time Handle Problem Language Result Execution time Memory
1070725 2024-08-22T17:19:05 Z zsombor Soccer Stadium (IOI23_soccer) C++17
0 / 100
 744 ms 1003604 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

int n, ans = 0;
vector<vector<bool> > t(3e3, vector<bool>(3e3, false));
vector<vector<vector<int> > > dp(3e3, vector<vector<int> >(3e3, vector<int>(4, -1e9)));

void u(int i, int l, int r, int x, int y, int val) {
    int j = 2 * n * l + r;
    int k = 2 * x + y;
    dp[i][j][k] = val;
}

int q(int i, int l, int r, int x, int y) {
    int j = 2 * n * l + r;
    int k = 2 * x + y;
    return dp[i][j][k];
}

void get_dp(int i, int l, int r, int x, int y) {
    for (int j = l; j <= r; j++) if (t[i][j]) return;
    int mx = 0, L1 = 1, Ln = n, R1 = 1, Rn = n;
    (x ? Ln = l : L1 = l);
    (y ? R1 = r : Rn = r);
    for (int L = L1; L <= Ln; L++) {
        for (int R = R1; R <= Rn; R++) {
            if (R < l || r < L) continue;
            mx = max(mx, q(i - 1, L, R, x, y));
        }
    }
    for (int X = 0; X <= x; X++) {
        for (int Y = 0; Y <= y; Y++) {
            mx = max(mx, q(i - 1, l, r, X, Y));
        }
    }
    mx += (r - l) + 1;
    u(i, l, r, x, y, mx);
    ans = max(ans, mx);
}

int biggest_stadium(int N, std::vector<std::vector<int> > F) {
    n = N;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            t[i][j] = F[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int l = 1; l <= n; l++) {
            for (int r = l; r <= n; r++) {
                for (int x = 0; x < 2; x++) {
                    for (int y = 0; y < 2; y++) {
                        get_dp(i, l, r, x, y);
                    }
                }
            }
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 495068 KB ok
2 Correct 488 ms 495204 KB ok
3 Correct 440 ms 494900 KB ok
4 Correct 443 ms 494928 KB ok
5 Correct 440 ms 494932 KB ok
6 Correct 450 ms 494932 KB ok
7 Runtime error 744 ms 1003604 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 495068 KB ok
2 Correct 488 ms 495204 KB ok
3 Correct 464 ms 494836 KB ok
4 Correct 481 ms 494928 KB ok
5 Incorrect 439 ms 494828 KB wrong
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 494996 KB ok
2 Correct 434 ms 495068 KB ok
3 Correct 488 ms 495204 KB ok
4 Correct 464 ms 494836 KB ok
5 Correct 481 ms 494928 KB ok
6 Incorrect 439 ms 494828 KB wrong
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 494996 KB ok
2 Correct 434 ms 495068 KB ok
3 Correct 488 ms 495204 KB ok
4 Correct 440 ms 494900 KB ok
5 Correct 443 ms 494928 KB ok
6 Correct 464 ms 494836 KB ok
7 Correct 481 ms 494928 KB ok
8 Incorrect 439 ms 494828 KB wrong
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 494996 KB ok
2 Correct 434 ms 495068 KB ok
3 Correct 488 ms 495204 KB ok
4 Correct 440 ms 494900 KB ok
5 Correct 443 ms 494928 KB ok
6 Correct 464 ms 494836 KB ok
7 Correct 481 ms 494928 KB ok
8 Incorrect 439 ms 494828 KB wrong
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 494996 KB ok
2 Correct 434 ms 495068 KB ok
3 Correct 488 ms 495204 KB ok
4 Correct 440 ms 494900 KB ok
5 Correct 443 ms 494928 KB ok
6 Correct 440 ms 494932 KB ok
7 Correct 450 ms 494932 KB ok
8 Runtime error 744 ms 1003604 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -