Submission #928502

#	Time	Username	Problem	Language	Result	Execution time	Memory
928502		abcvuitunggio	Soccer Stadium (IOI23_soccer)	C++17	77.50 / 100	1413 ms	356332 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];
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=0;k<=(n<501)*n;k++)
        for (int i=n;i>=0;i--){
            int x=(n>500?S:k),y=(n>500?S:k);
            dp[i][i].push_back(0);
            for (int j=n;j>i;j--){
                while (x&&s[j][x-1]==s[i][x-1])
                    x--;
                while (y<n&&s[j][y]==s[i][y])
                    y++;
                dp[i][j].push_back(y-x);
            }
            for (int j=i+1;j<=n;j++){
                dp[i][j][k]+=max(dp[i+1][j][k],dp[i][j-1][k]);
                ans=max(ans,dp[i][j][k]);
            }
        }
    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