제출 #928191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928191		abcvuitunggio	축구 경기장 (IOI23_soccer)	C++17	48 / 100	4553 ms	2063332 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 f(int i, int j, int k){
    if (i==j)
        return 0;
    if (dp[i][j][k]!=-1)
        return dp[i][j][k];
    return dp[i][j][k]=max(f(i+1,j,l[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),f(i,j-1,l[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));
}
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 i=0;i<n;i++)
        for (int j=n;j>i;j--)
            for (int k=0;k<=n;k++)
                dp[i][j][k]=-1;
    for (int i=0;i<=n;i++)
        ans=max(ans,f(0,n,l[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: 0 / 16
• Subtask 6: 0 / 30