Submission #928404

#	Time	Username	Problem	Language	Result	Execution time	Memory
928404		abcvuitunggio	Soccer Stadium (IOI23_soccer)	C++17	77.50 / 100	3675 ms	1053652 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2006;
int n,ans,s[mxn][mxn];
vector <int> dp[mxn][mxn],l[mxn][mxn],r[mxn][mxn];
int biggest_stadium(int N, vector <vector <int>> F){
    n=N;
    int S=0;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++){
            s[i+1][j]=s[i][j]+F[i][j];
            if (!F[i][j])
                S=j;
        }
    for (int k=(n>500)*S;k<=(n>500?S:n);k++)
        for (int i=0;i<=n;i++){
            int x=k,y=k;
            for (int j=n;j>=i;j--){
                while (x&&s[j][x-1]==s[i][x-1])
                    x--;
                l[i][j].push_back(x);
                while (y<n&&s[j][y]==s[i][y])
                    y++;
                r[i][j].push_back(y);
                dp[i][j].push_back(0);
            }
        }
    for (int L=1;L<=n;L++)
        for (int i=0;i+L<=n;i++)
            for (int k=0;k<=(n<=500)*n;k++){
                int j=i+L;
                dp[i][j][k]=max(dp[i+1][j][k],dp[i][j-1][k])+r[i][j][k]-l[i][j][k];
            }
    for (int i=0;i<=(n<=500)*n;i++)
        ans=max(ans,dp[0][n][i]);
    return ans;
}

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