제출 #1221593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221593		thelegendary08	Soccer Stadium (IOI23_soccer)	C++17	35.50 / 100	1172 ms	94860 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0;i<n;i++)
#define FOR(i, k, n) for(int i = k;i<n;i++)
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define mp make_pair
#define vpii vector<pii>
#define vvi vector<vi>
using namespace std;
bool solve(pii a, pii b, vvi &psr, vvi &psc){
	if(a.first == b.first || a.second == b.second){
		return 1;
	}
	
	int s1 = psr[a.first][max(a.second, b.second) + 1] - psr[a.first][min(a.second, b.second)] +
			 psc[b.second][max(a.first, b.first) + 1] - psc[b.second][min(a.first, b.first)];
	int s2 = psc[a.second][max(a.first, b.first) + 1] - psc[a.second][min(a.first, b.first)] + 
			 psr[b.first][max(a.second, b.second) + 1] - psr[b.first][min(a.second, b.second)];
	if(s1 == 0 || s2 == 0)return 1;
	else return 0;
}
signed biggest_stadium(signed n, std::vector<std::vector<signed>> v)
{
	int s = 0;
	pii p = mp(-1,-1);
	f0r(i,n){
		f0r(j,n){
			s += v[i][j];
			if(v[i][j])p = mp(i,j);
		}
	}
	if(s == 0){
		return n * n;
	}
	else if(s == 1){
		int a = min(p.first+1, n-p.first);
		int b = min(p.second+1, n-p.second);
		return n * n - a * b;
	}
	else if(n <= 3){
		int ans = 0; 
		f0r(i, (1LL << (n * n))){
			vector<vector<signed>>V(n, vector<signed>(n));
			int sum = 0;
			bool oke = 1; 
			f0r(j, n * n){
				if((1LL << j) & i){
					V[j/n][j%n] = 1; 
				}
				else{
					V[j/n][j%n] = 0; sum++;
					if(v[j/n][j%n] == 1)oke = 0;
				}
				
			}
			if(oke){
				vector<vector<signed>>v = V;
				bool ok = 1;
				f0r(i,n){
					bool off = 0;
					f0r(j,n){
						if(off){
							if(v[i][j] == 0 && v[i][j-1] == 1){
								ok = 0;
							}
						}
						if(v[i][j] == 0){
							off = 1;
						}
					}
				}
				f0r(j,n){
					bool off = 0;
					f0r(i,n){
						if(off){
							if(v[i][j] == 0 && v[i-1][j] == 1){
								ok = 0;
							}
						}
						if(v[i][j] == 0){
							off = 1;
						}
					}
				}
				
				if(!ok){
					continue;
				}
				else{
					vpii pts;
					vvi psr; //fix i move j 
					vvi psc; //fix j move i
					f0r(i,n){
						vi ps(n+1);
						int la = -1;
						f0r(j,n){
							ps[j+1] = ps[j] + v[i][j];
							if(v[i][j] == 0)la = j;
						}
						int fi = -1;
						f0r(j,n){
							if(v[i][j] == 0){
								fi = j; break;
							}
						}
						if(la != -1){
							pts.pb(mp(i, la));
						}
						if(fi != -1 && fi != la){
							pts.pb(mp(i, fi));
						}
						psr.pb(ps);
					}
					
					f0r(i,n){
						vi ps(n+1);
						int la = -1;
						f0r(j,n){
							ps[j+1] = ps[j] + v[j][i];
							if(v[j][i] == 0)la = j;
						}
						int fi = -1;
						f0r(j,n){
							if(v[j][i] == 0){
								fi = j; break;
							}
						}
						if(la != -1){
							pts.pb(mp(la, i));
						}
						if(fi != -1 && fi != la){
							pts.pb(mp(fi, i));
						}
						psc.pb(ps);
					}
					
					f0r(i,pts.size()){
						f0r(j,pts.size()){
							if(i != j){
								if(!solve(pts[i], pts[j], psr, psc)){
									ok = 0;
								}
							}
						}
					}
					if(ok){
						ans = max(ans, sum);
					}
					
				}
			}
		}
		return ans;
	}
	else{
		bool ok = 1;
		f0r(i,n){
			bool off = 0;
			f0r(j,n){
				if(off){
					if(v[i][j] == 0 && v[i][j-1] == 1){
						ok = 0;
					}
				}
				if(v[i][j] == 0){
					off = 1;
				}
			}
		}
		f0r(j,n){
			bool off = 0;
			f0r(i,n){
				if(off){
					if(v[i][j] == 0 && v[i-1][j] == 1){
						ok = 0;
					}
				}
				if(v[i][j] == 0){
					off = 1;
				}
			}
		}
		
		if(!ok){
			return 0;
		}
		else{
			vpii pts;
			vvi psr; //fix i move j 
			vvi psc; //fix j move i
			f0r(i,n){
				vi ps(n+1);
				int la = -1;
				f0r(j,n){
					ps[j+1] = ps[j] + v[i][j];
					if(v[i][j] == 0)la = j;
				}
				int fi = -1;
				f0r(j,n){
					if(v[i][j] == 0){
						fi = j; break;
					}
				}
				if(la != -1){
					pts.pb(mp(i, la));
				}
				if(fi != -1 && fi != la){
					pts.pb(mp(i, fi));
				}
				psr.pb(ps);
			}
			
			f0r(i,n){
				vi ps(n+1);
				int la = -1;
				f0r(j,n){
					ps[j+1] = ps[j] + v[j][i];
					if(v[j][i] == 0)la = j;
				}
				int fi = -1;
				f0r(j,n){
					if(v[j][i] == 0){
						fi = j; break;
					}
				}
				if(la != -1){
					pts.pb(mp(la, i));
				}
				if(fi != -1 && fi != la){
					pts.pb(mp(fi, i));
				}
				psc.pb(ps);
			}
			
			f0r(i,pts.size()){
				f0r(j,pts.size()){
					if(i != j){
						if(!solve(pts[i], pts[j], psr, psc)){
							ok = 0;
						}
					}
				}
			}
			if(ok)return n*n-s;
			else return 0;
			
		}
	}
    return 0;
}

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