제출 #928393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928393		abcvuitunggio	Soccer Stadium (IOI23_soccer)	C++17	30 / 100	291 ms	579068 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 sum(int l, int r, int i){
    return s[r][i]-s[l][i];
}
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?0:S);k<=(n<=500?n:S);k++)
        for (int i=0;i<=n;i++){
            int x=k,y=k;
            for (int j=n;j>=i;j--){
                while (x&&!sum(i,j,x-1))
                    x--;
                l[i][j].push_back(x);
                while (y<n&&!sum(i,j,y))
                    y++;
                r[i][j].push_back(y);
                dp[i][j].assign((n<=500?n:0),0);
            }
        }
    for (int L=0;L<n;L++)
        for (int i=0;i+L+1<=n;i++)
            for (int k=0;k<=(n<=500?n:0);k++){
                int j=i+L+1;
                dp[i][j][k]=max(dp[i+1][j][k]+(l[i][j][k]-l[i+1][j][k]+r[i+1][j][k]-r[i][j][k])*L,dp[i][j-1][k]+(l[i][j][k]-l[i][j-1][k]+r[i][j-1][k]-r[i][j][k])*L);
            }
    for (int i=0;i<=(n<=500?n:0);i++)
        ans=max(ans,dp[0][n][i]+(r[0][n][i]-l[0][n][i])*n);
    return ans;
}

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