Submission #845759

#	Time	Username	Problem	Language	Result	Execution time	Memory
845759		Sorting	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	27 ms	13396 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 30;

bool f[N][N];
int prefix[N][N];
int n;

pair<int, bool> dp[N][N][N][N];

int get_sum(int i, int l, int r){
    if(l == 0)
        return prefix[i][r];
    return prefix[i][r] - prefix[i][l - 1];
}

bool bad(int l1, int r1, int l2, int r2){
    if(l1 <= l2 && r2 <= r1)
        return false;
    if(l2 <= l1 && r1 <= r2)
        return false;
    return true;
}

int solve(int i, int j, int l, int r){
    auto &[ans, solved] = dp[i][j][l][r];
    if(solved)
        return ans;

    ans = 0;
    solved = true;
    if(l != r){
        ans = max(ans, solve(i, j, l + 1, r));
        ans = max(ans, solve(i, j, l, r - 1));
    }

    if(i != 0){
        int sum = get_sum(i - 1, l, r);
        if(!sum){
            ans = max(ans, solve(i - 1, j, l, r) + r - l + 1);
        }
    }
    if(j != n - 1){
        int sum = get_sum(j + 1, l, r);
        if(!sum){
            ans = max(ans, solve(i, j + 1, l, r) + r - l + 1);
        }
    }

    return ans;
}

int biggest_stadium(int _N, std::vector<std::vector<int>> F){
    n = _N;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            f[i][j] = F[i][j];

    for(int i = 0; i < n; ++i){
        prefix[i][0] = f[i][0];
        for(int j = 1; j < n; ++j)
            prefix[i][j] = prefix[i][j - 1] + f[i][j];
    }

    int ans = 0;
    for(int i = 0; i < n; ++i){
        for(int l = 0; l < n; ++l){
            for(int r = l; r < n; ++r){
                if(f[i][r])
                    break;
               ans = max(ans, solve(i, i, l, r) + r - l + 1);
            }
        }
    }

    return ans;
}
/*
3
1 1 1
1 1 1
1 1 1
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30