Submission #842246

#	Time	Username	Problem	Language	Result	Execution time	Memory
842246		WongChun1234	Soccer Stadium (IOI23_soccer)	C++17	64 / 100	546 ms	98520 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
const int N=550;
int n,psum[N][N],l[N][N],r[N][N],currl[N][N],currr[N][N],dp[N][N],ans;
vector<vector<int>> f;
int get(int _x1,int _y1,int _x2,int _y2){
    if (_x1>_x2) swap(_x1,_x2);
    if (_y1>_y2) swap(_y1,_y2);
    return psum[_x2][_y2]-psum[_x1-1][_y2]-psum[_x2][_y1-1]+psum[_x1-1][_y1+1];
}

int biggest_stadium(int N, vector<vector<int>> F) {
    n=N;
    f=F;
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){
        psum[i][j]=psum[i-1][j]+psum[i][j-1]+F[i-1][j-1]-psum[i-1][j-1];
    }
    //l: first block r: last space
    for (int i=1;i<=n;i++){
        l[i][0]=0;
        for (int j=1;j<=n;j++) l[i][j]=(F[i-1][j-1]?j:l[i][j-1]);
        r[i][n+1]=n;
        for (int j=n;j>=1;j--) r[i][j]=(F[i-1][j-1]?j-1:r[i][j+1]);
    }
    for (int y=1;y<=n;y++){
        for (int i=1;i<=n;i++) currl[i][i]=l[i][y],currr[i][i]=r[i][y];
        for (int i=n;i>=1;i--) for (int j=i+1;j<=n;j++){
            currl[i][j]=max(currl[i+1][j],currl[i][j-1]);
            currr[i][j]=min(currr[i+1][j],currr[i][j-1]);
        }
        for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) dp[i][j]=0;
        for (int i=1;i<=n;i++) dp[i][i]=currr[i][i]-currl[i][i];
        for (int i=n;i>=1;i--) for (int j=i+1;j<=n;j++){
            dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
            dp[i][j]=max(dp[i][j],dp[i+1][j]+currr[i][j]-currl[i][j]);
            dp[i][j]=max(dp[i][j],dp[i][j-1]+currr[i][j]-currl[i][j]);
        }
        ans=max(ans,dp[1][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