제출 #1212857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1212857		Aviansh	축구 경기장 (IOI23_soccer)	C++20	0 / 100	4591 ms	6300 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

int biggest_stadium(int n, vector<vector<int>> F)
{
    int lef[n][n];
    int rig[n][n];
    for(int i = 0;i<n;i++){
        int las = -1;
        for(int j = 0;j<n;j++){
            if(F[i][j])
                las=j;
            lef[i][j]=las;
        }
        las=n;
        for(int j = n-1;j>=0;j--){
            if(F[i][j])
                las=j;
            rig[i][j]=las;
        }
    }
    int ans = 0;
    for(int k = 0;k<n;k++){
        int curr = 0;
        for(int l = 0;l<=k;l++){
            for(int r = k;r<n;r++){
                vector<int>lens(r-l+1);
                for(int i = l;i<=r;i++){
                    int len = rig[i][k]-lef[i][k]-1;
                    lens[i-l]=len;
                }
                int m = r-l+1;
                int dp[m][n+1];
                //{considered lens till i, maximum height}
                for(int i = 0;i<m;i++){
                    dp[i][0]=0;
                    int bslas = 0;
                    for(int j = 1;j<=n;j++){
                        dp[i][j]=0;
                        if(j>lens[i])
                            continue;
                        if(i){
                            if(dp[i-1][bslas]<dp[i-1][j]){
                                bslas=j;
                            }
                            dp[i][j]=max(dp[i][j],dp[i-1][bslas]+j);
                        }
                        else{
                            dp[i][j]=j;
                        }
                    }
                }
                int dp2[m][n+1];
                //{considered lens till i, maximum height}
                for(int i = m-1;i>=0;i--){
                    dp2[i][0]=0;
                    int bslas = 0;
                    for(int j = 1;j<=n;j++){
                        dp2[i][j]=0;
                        if(j>lens[i])
                            continue;
                        if(i<m-1){
                            if(dp2[i+1][bslas]<dp2[i+1][j]){
                                bslas=j;
                            }
                            dp2[i][j]=max(dp2[i][j],dp2[i+1][bslas]+j);
                        }
                        else{
                            dp2[i][j]=j;
                        }
                    }
                }
                for(int i = 0;i<m;i++){
                    for(int j = 0;j<=n;j++){
                        ans=max(ans,dp[i][j]+dp2[i][j]-j);
                    }
                }
            }
        }
    }
    return ans;
}

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