제출 #1010534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010534		ttamx	축구 경기장 (IOI23_soccer)	C++17	100 / 100	518 ms	175188 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
#define cerr if(0)cerr

using namespace std;

const int N=2005;

int n;
int a[N][N];
int top[N][N],bot[N][N],pre[N][N][2],dp[N][N];
vector<pair<int,int>> rect[N];
int ans;

int biggest_stadium(int _n,vector<vector<int>> _a){
    n=_n;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=_a[i-1][j-1]^1;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)top[i][j]=a[i][j]?a[i-1][j]?top[i-1][j]:i:top[i-1][j];
    for(int i=1;i<=n;i++)bot[n+1][i]=n+1;
    for(int i=n;i>=1;i--)for(int j=1;j<=n;j++)bot[i][j]=a[i][j]?a[i+1][j]?bot[i+1][j]:i:bot[i+1][j];
    for(int i=1;i<=n;i++){
        int t=0,b=n+1;
        for(int j=1;j<=n;j++){
            for(int x=0;x<2;x++)pre[i][j][x]=a[i][j]==x?j:pre[i][j-1][x];
            if(a[i][j]){
                if(a[i][j-1]){
                    top[i][j]=max(top[i][j],top[i][j-1]);
                    bot[i][j]=min(bot[i][j],bot[i][j-1]);
                }
                rect[j-pre[i][j][0]].emplace_back(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cerr << bot[i][j] << " \n"[j==n];
    cerr << "\n";
    for(int w=n;w>=1;w--)for(auto [i,j]:rect[w]){
        int l=pre[i][j][0]+1,r=j,t=top[i][j],b=bot[i][j];
        int lw=l>1?bot[i][l-1]+1:i+1;
        cerr << "(" << i << ", " << j << ") ";
        cerr << l << " " << r << " " << t << " " << b << " : " << lw << "\n";
        if(lw<=b){
            cerr << "SKIP TO " << lw << " " << j << "\n";
            dp[lw][j]=max(dp[lw][j],dp[i][j]);
            continue;
        }
        if(a[i][j+1]&&top[i][j+1]<=t&&bot[i][j+1]>=b)continue;
        int h=b-t+1;
        int res=w*h+dp[i][j];
        cerr << w*h << " + " << dp[i][j] << " = " << res << "\n";
        ans=max(ans,res);
        if(t>1){
            for(int nr=pre[t-1][r][1],nl;nr>=l;nr=pre[t-1][nl][1]){
                nl=max(l-1,pre[t-1][nr][0]);
                int p=nl>=l?t-1:i;
                dp[p][nr]=max(dp[p][nr],res-(nr-nl)*h);
            }
        }
        if(b<n){
            for(int nr=pre[b+1][r][1],nl;nr>=l;nr=pre[b+1][nl][1]){
                nl=max(l-1,pre[b+1][nr][0]);
                int p=nl>=l?b+1:i;
                dp[p][nr]=max(dp[p][nr],res-(nr-nl)*h);
            }
        }
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:22:13: warning: unused variable 't' [-Wunused-variable]
   22 |         int t=0,b=n+1;
      |             ^
soccer.cpp:22:17: warning: unused variable 'b' [-Wunused-variable]
   22 |         int t=0,b=n+1;
      |                 ^

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