제출 #1010504

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

soccer

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

using namespace std;

const int N=2005;

int n;
int a[N][N];
int top[N][N],bot[N][N],pre[N][N][2];
vector<pair<int,int>> rect[N];
int ans;
map<tuple<int,int,int,int>,int> mem;
map<tuple<int,int,int,int>,bool> vis;

int& get(int i,int j){
    int l=pre[i][j][0]+1,r=j,t=top[i][j],b=bot[i][j];
    return mem[{l,r,t,b}];
}

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]?min(i,i>1?top[i-1][j]:n+1):n+1;
    for(int i=n;i>=1;i--)for(int j=1;j<=n;j++)bot[i][j]=a[i][j]?max(i,bot[i+1][j]):0;
    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 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];
        if(vis[{l,r,t,b}])continue;
        vis[{l,r,t,b}]=true;
        int h=b-t+1;
        int res=w*h+get(i,j);
        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;
                get(p,nr)=max(get(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;
                get(p,nr)=max(get(p,nr),res-(nr-nl)*h);
            }
        }
    }
    return ans;
}

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

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