제출 #928186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928186		abcvuitunggio	축구 경기장 (IOI23_soccer)	C++17	64 / 100	1872 ms	2059232 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=502;
int n,ans,dp[mxn][mxn][mxn],s[2001][2001],l[mxn][mxn][mxn],r[mxn][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;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            s[i+1][j]=s[i][j]+F[i][j];
    for (int k=0;k<=n;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][k]=x;
                while (y<n&&!sum(i,j,y))
                    y++;
                r[i][j][k]=y;
            }
        }
    for (int L=1;L<=n;L++)
        for (int i=0;i<n;i++)
            for (int k=0;k<=n;k++){
                int j=i+L;
                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])*(j-i-1),dp[i][j-1][k]+(l[i][j][k]-l[i][j-1][k]+r[i][j-1][k]-r[i][j][k])*(j-i-1));
            }
    for (int i=0;i<=n;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: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 0 / 30