oj.uz

Submission #1059719

# Submission time Handle Problem Language Result Execution time Memory
1059719 2024-08-15T07:27:37 Z dozer Soccer Stadium (IOI23_soccer) C++17
0 / 100
 171 ms 24660 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " " 
#define endl "\n"
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 35

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;

int dp[2][MAXN][MAXN][MAXN][MAXN], prv[2][MAXN][MAXN][MAXN][MAXN];


int biggest_stadium(int N, vector<std::vector<int>> F)
{   
    int n = N;
    vector<pii> v;
    vector<vector<int>> pre = F;
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++) pre[i][j] += pre[i][j - 1];

    for (int i = 0; i < n; i++){
        for (int j = i; j < n; j++)
            v.pb({i, j});
    }

    sort(v.begin(), v.end(), [&](pii a, pii b){
        return (a.nd - a.st) < (b.nd - b.st);
    });

    int ans = 0;
    for (int i = n - 1; i >= 0; i--){
        for (int a = 0; a < n; a++){
            for (int b = a; b < n; b++){
                for (auto j : v){
                    int l = j.st, r = j.nd;
                    if (l < a && r < b) continue;
                    if (l > a && r > b) continue;
                    dp[0][a][b][l][r] = 0;
                    int sum = pre[i][r];
                    if (l > 0) sum -= pre[i][l - 1];
                    if (sum == 0) dp[0][a][b][l][r] = (r - l + 1) + prv[0][a][b][l][r];
                    if (r > l) dp[0][a][b][l][r] = max(dp[0][a][b][l][r], max(dp[0][a][b][l][r - 1], dp[0][a][b][l + 1][r]));
                    if (a == l && b == r) ans = max(ans, dp[0][a][b][l][r]);
                }

                reverse(v.begin(), v.end());
                for (auto j : v){
                    int l = j.st, r = j.nd;
                    dp[1][a][b][l][r] = 0;
                    if (l < a && r < b) continue;
                    if (l > a && r > b) continue;
                    int sum = pre[i][r];
                    if (l > 0) sum -= pre[i][l - 1];
                    if (sum == 0) dp[1][a][b][l][r] = (r - l + 1) + max(prv[0][a][b][l][r], prv[1][a][b][l][r]);
                    if (l > 0) dp[1][a][b][l][r] = max(dp[1][a][b][l][r], dp[1][a][b][l - 1][r]);
                    if (r < n - 1) dp[1][a][b][l][r] = max(dp[1][a][b][l][r], dp[1][a][b][l][r + 1]);
                    if (a == l && b == r) ans = max(ans, dp[1][a][b][l][r]);
                }
                reverse(v.begin(), v.end());
                

            }
        }
        swap(dp, prv);
    }

    return ans;
}
/*
int main()
{
    fileio();
    int N;
    assert(1 == scanf("%d", &N));
    std::vector<std::vector<int>> F(N, std::vector<int>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            assert(1 == scanf("%d", &F[i][j]));
        }
    }
    fclose(stdin);

    int res = biggest_stadium(N, F);

    printf("%d\n", res);
    fclose(stdout);
    return 0;
}
*/

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23900 KB ok
2 Correct 17 ms 23696 KB ok
3 Correct 33 ms 23900 KB ok
4 Correct 33 ms 23900 KB ok
5 Correct 11 ms 23896 KB ok
6 Correct 16 ms 23900 KB ok
7 Runtime error 171 ms 24660 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 16 ms 23900 KB ok
2 Correct 17 ms 23696 KB ok
3 Correct 16 ms 23896 KB ok
4 Correct 17 ms 23900 KB ok
5 Correct 25 ms 23912 KB ok
6 Correct 16 ms 23900 KB ok
7 Incorrect 17 ms 23736 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23900 KB ok
2 Correct 16 ms 23900 KB ok
3 Correct 17 ms 23696 KB ok
4 Correct 16 ms 23896 KB ok
5 Correct 17 ms 23900 KB ok
6 Correct 25 ms 23912 KB ok
7 Correct 16 ms 23900 KB ok
8 Incorrect 17 ms 23736 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23900 KB ok
2 Correct 16 ms 23900 KB ok
3 Correct 17 ms 23696 KB ok
4 Correct 33 ms 23900 KB ok
5 Correct 33 ms 23900 KB ok
6 Correct 16 ms 23896 KB ok
7 Correct 17 ms 23900 KB ok
8 Correct 25 ms 23912 KB ok
9 Correct 16 ms 23900 KB ok
10 Incorrect 17 ms 23736 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23900 KB ok
2 Correct 16 ms 23900 KB ok
3 Correct 17 ms 23696 KB ok
4 Correct 33 ms 23900 KB ok
5 Correct 33 ms 23900 KB ok
6 Correct 16 ms 23896 KB ok
7 Correct 17 ms 23900 KB ok
8 Correct 25 ms 23912 KB ok
9 Correct 16 ms 23900 KB ok
10 Incorrect 17 ms 23736 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23900 KB ok
2 Correct 16 ms 23900 KB ok
3 Correct 17 ms 23696 KB ok
4 Correct 33 ms 23900 KB ok
5 Correct 33 ms 23900 KB ok
6 Correct 11 ms 23896 KB ok
7 Correct 16 ms 23900 KB ok
8 Runtime error 171 ms 24660 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -