Submission #840860

#	Time	Username	Problem	Language	Result	Execution time	Memory
840860		Lucpp	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	4573 ms	4224 KiB

soccer

#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;

constexpr int MAX = 30;
constexpr int inf = 1e7;

int dp[MAX][MAX+1][MAX][MAX+1];

int biggest_stadium(int N, vector<vector<int>> F){
    for(int d = N; d >= 1; d--){
        for(int l = 0; l+d <= N; l++){
            int r = l+d;
            for(int a = 0; a < N; a++){
                for(int b = a+1; b <= N; b++){
                    int res = 0;
                    auto calc = [&](int x, int y1, int y2){
                        int last = a;
                        for(int i = a; i < b; i++){
                            if(!F[x][i]) continue;
                            if(i > last) res = max(res, dp[y1][y2][last][i] + i-last);
                            last = i+1;
                        }
                        if(b > last) res = max(res, dp[y1][y2][last][b] + b-last);
                    };
                    if(l > 0) calc(l-1, l-1, r);
                    if(r < N) calc(r, l, r+1);
                    dp[l][r][a][b] = res;
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < N; i++){
        int last = 0;
        for(int j = 0; j < N; j++){
            if(!F[i][j]) continue;
            if(j > last) ans = max(ans, dp[i][i+1][last][j] + j-last);
            last = j+1;
        }
        if(N > last) ans = max(ans, dp[i][i+1][last][N] + N-last);
    }
    return ans;
}

• 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