제출 #1233753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233753		nikulid	Soccer Stadium (IOI23_soccer)	C++20	6 / 100	191 ms	31772 KiB

soccer

#include "soccer.h"
#include <iostream>

using namespace std;

#define pb push_back
#define mp make_pair
#define plist(x) if(1==0){for(auto e:x)cout<<e<<",";cout<<"\n";}
#define dout if(1==0)cout
// (y,x)

int biggest_stadium(int n, vector<vector<int>> f){
	vector<int> treesH(1,-1), treesV(1,-1); // H means the rows themselves are horizontal (!)
	vector<int> tH(n,0), tV(n,0);
	pair<int, int> tree = mp(-1,-1);
	for(int y=0; y<n; y++){
		for(int x=0; x<n; x++){
			if(f[y][x]){
				tree = mp(y,x);
				treesH.pb(x);
				treesV.pb(y);
				tH[y]=1;
				tV[x]=1;
			}
		}
	}
	cerr<<"treesH: ";plist(treesH);
	cerr<<"treesV: ";plist(treesV);
	vector<int> gridV, gridH;
	for(int x=0; x<=n; x++){
		if(x==0 || (x>0 && tV[x-1]) || (x<n && tV[x]) || x==n){
			gridV.pb(x);
		}
	}
	for(int y=0; y<=n; y++){
		if(y==0 || (y>0 && tH[y-1]) || (y<n && tH[y]) || y==n){
			gridH.pb(y);
		}
	}
	cerr<<"gridH: ";plist(gridH);
	cerr<<"gridV: ";plist(gridV);
	int N=gridH.size()-1;
	int M=gridV.size()-1;
	
	vector<vector<int>> ar(N);
	for(int y=0; y<N; y++){
		for(int x=0; x<M; x++){
			ar[y].pb((gridV[x+1]-gridV[x])*(gridH[y+1]-gridH[y]));
			if(ar[y][x]==1 && f[gridH[y]][gridV[x]]/*..*/){
				ar[y][x]=0;
			}
		}
	}

	if(1==1){
		cerr<<"here it comes:\n";
		for(int y=0; y<N; y++){
			for(int x=0; x<M; x++){
				cerr<<ar[y][x]<<" ";
			}
			cerr<<"\n";
		}
	}
	
	swap(n,N);
	int m=M;

	int answer=0, cursum;
	int low,high,curlow,curhigh;
	dout<<"(n,m) >> ("<<n<<","<<m<<")\n";
	for(int y=0; y<n; y++){
		for(int x=0; x<m; x++){
			// what if this was the central square?
			if(ar[y][x]==0)continue; // can't play in a tree :(
			cursum=0;
			low=-1; high=n;

			// find highs and lows (and do search on this column)
			for(int ny=y; ny>low; ny--){
				if(ar[ny][x]==0){
					low=ny;
				} else{
					cursum += ar[ny][x];
				}
			}
			for(int ny=y+1; ny<high; ny++){
				if(ar[ny][x]==0){
					high=ny;
				} else{
					cursum += ar[ny][x];
				}
			}

			// go to the RIGHT
			curhigh = high;
			curlow = low;
			for(int nx=x+1; nx<m; nx++){
				if(ar[y][nx]==0)break;
				for(int ny=y; ny>curlow; ny--){
					if(ar[ny][nx]==0){
						curlow=ny;
					} else{
						cursum += ar[ny][nx];
					}
				}
				for(int ny=y+1; ny<curhigh; ny++){
					if(ar[ny][nx]==0){
						curhigh=ny;
					} else{
						cursum += ar[ny][nx];
					}
				}
			}

			// go to the LEFT
			curhigh = high;
			curlow = low;
			for(int nx=x-1; nx>-1; nx--){
				if(ar[y][nx]==0)break;
				for(int ny=y; ny>curlow; ny--){
					if(ar[ny][nx]==0){
						curlow=ny;
					} else{
						cursum += ar[ny][nx];
					}
				}
				for(int ny=y+1; ny<curhigh; ny++){
					if(ar[ny][nx]==0){
						curhigh=ny;
					} else{
						cursum += ar[ny][nx];
					}
				}
			}
			answer = max(answer, cursum);
		}
	}

	return answer;
}

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