Submission #1058398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058398		jcelin	Soccer Stadium (IOI23_soccer)	C++17	1.50 / 100	162 ms	55380 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 2007;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int mat[MAXN][MAXN], n;
ii p[MAXN];

int prvi(){
	int ans = inf;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(mat[i][j]){
				ans = min(ans, i * j);
				ans = min(ans, (n - i + 1) * j);
				ans = min(ans, (n - i + 1) * (n - j + 1));
				ans = min(ans, i * (n - j + 1));
			}
		}
	}
	return n * n - ans;
}

int leng(int id){
	return p[id].Y - p[id].X + 1;
}

bool pod(int a, int b){
	return p[b].X <= p[a].X and p[b].Y >= p[a].Y;
}

bool dobre(){
	int opt = -1;
	for(int i=1; i<=n; i++){
		p[i] = {inf, -inf};
		int j = 1;
		while(j <= n and mat[i][j]) j++;
		
		if(j > n) continue;
		p[i].X = j;
		
		j = n;
		while(j and mat[i][j]) j--;
		p[i].Y = j;
		
		for(j = p[i].X; j<=p[i].Y; j++) if(mat[i][j]) return 0;
		opt = i;
	}
	if(opt == -1) return 1;
	
	for(int i=1; i<=n; i++) if(leng(i) > leng(opt)) opt = i;
	
	for(int i=opt-1; i; i--) if(!pod(i, i + 1)) return 0;
	for(int i=opt+1; i<=n; i++) if(!pod(i, i - 1)) return 0;
	return 1;
}

int biggest_stadium(int _n, vector<vi> m){
	int num = 0;
	n = _n;
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
		mat[i][j] = m[i - 1][j - 1];
		num += !mat[i][j];
	}
	
	if(dobre()) return num;
	if(num == 1) return prvi();
	if(n > 510) return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:95:1: warning: control reaches end of non-void function [-Wreturn-type]
   95 | }
      | ^

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