Submission #1178089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178089		Kaztaev_Alisher	Soccer Stadium (IOI23_soccer)	C++20	8 / 100	13 ms	2372 KiB

soccer

#include <bits/stdc++.h>

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second

using namespace std;
using ll = long long;

const ll N = 55 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7;

int n , pr[N][N] , a[N][N] , l[N][N], r[N][N] , up[N][N] , dn[N][N] , b[N] , c[N];
// int lft[N] , rght[N];
// int lft2[N] , rght2[N];
// void build(vector<int> x){
	// stack<pair<int,int>> st;
	// int sum = 0;
	// st.push({0,-1});
	// for(int i = 0; i < x.size(); i++){
		// while(st.size() && st.top().F > x[i]){
			// int pos = st.top().S;
			// st.pop();
			// sum -= (pos-st.top().S)*x[pos];
		// }
		// sum += (i-st.top().S)*x[i];
		// st.push({x[i],i});
		// lft[i] = sum;
	// }
	// while(st.size()) st.pop();
	// sum = 0;
	// st.push({0,x.size()});
	// for(int i = x.size()-1; i >= 0; i--){
		// while(st.size() && st.top().F > x[i]){
			// int pos = st.top().S;
			// st.pop();
			// sum -= (st.top().S-pos)*x[pos];
		// }
		// sum += (st.top().S-i)*x[i];
		// st.push({x[i],i});
		// rght[i] = sum;
	// }
// }
int get(vector<int> x , vector<int> y){
	// build(x);
	// for(int i = 0; i < x.size(); i++) {
		// lft2[i] = lft[i];
		// rght2[i] = rght[i];
	// } 
	// build(y);
	int ans = 0;
	for(int i = 0; i < x.size(); i++){
		int cur = x[i] , sum = 0;
		for(int j = i; j >= 0; j--){
			cur = min(cur , x[j]);
			b[j] = cur;
			sum += cur;
		}
		cur = x[i];
		for(int j = i+1; j < x.size(); j++){
			cur = min(cur , x[j]);
			b[j] = cur;
			sum += cur;
		}
		cur = y[i];
		for(int j = i; j >= 0; j--){
			cur = min(cur , y[j]);
			c[j] = cur;
			sum += cur;
		}
		cur = y[i];
		for(int j = i+1; j < x.size(); j++){
			cur = min(cur , y[j]);
			c[j] = cur;
			sum += cur;
		}
		for(int len = 1; len <= min(c[i],b[i]); len++){
			int l = i , r = i;
			int l2 = i , r2 = i;
			for(int j = 0; j < n; j++){
				if(b[j] >= len){
					l = min(l , j);
					r = max(r , j);
				}
				if(c[j] >= len){
					l2 = min(l2 , j);
					r2 = max(r2 , j);
				}
			}
			if(l <= l2 && r2 <= r) continue;
			if(l2 <= l && r <= r2) continue;
			if(l < l2){
				int bb = 0 , cc = 0;
				for(int j = l; j < l2; j++){
					bb += b[j]-len+1;
				}
				for(int j = r+1; j <= r2; j++){
					cc += c[j]-len+1;
				}
				sum -= min(bb,cc);
				if(bb <= cc){
					for(int j = l; j < l2; j++){
						b[j] = len;
					}
				} else {
					for(int j = r+1; j <= r2; j++){
						c[j] = len;
					}	
				}
			} else {
				int bb = 0 , cc = 0;
				for(int j = l2; j < l; j++){
					cc += c[j]-len+1;
				}
				for(int j = r2+1; j <= r; j++){
					bb += b[j]-len+1;
				}
				sum -= min(bb,cc);
				if(bb <= cc){
					for(int j = r2+1; j <= r; j++){
						b[j] = len;
					}	
				} else {
					for(int j = l2; j < l; j++){
						c[j] = len;
					}
				}
			}
		}
		ans = max(ans , sum);
	}
	return ans;
}
int solve(){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			pr[i][j] = a[i][j] + pr[i-1][j] + pr[i][j-1] - pr[i-1][j-1];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			up[i][j] = up[i-1][j];
			if(up[i][j] == 0) up[i][j] = i;
			if(a[i][j] == 1) up[i][j] = 0;
		}	
	}
	for(int i = n; i >= 1; i--){
		for(int j = 1; j <= n; j++){
			dn[i][j] = dn[i+1][j];
			if(dn[i][j] == 0) dn[i][j] = i;
			if(a[i][j] == 1) dn[i][j] = 0;
		}	
	}
	for(int j = 1; j <= n; j++){
		for(int i = 1; i <= n; i++){
			l[i][j] = l[i][j-1];
			if(l[i][j] == 0) l[i][j] = j;
			if(a[i][j] == 1) l[i][j] = 0;
		}
	}
	for(int j = n; j >= 1; j--){
		for(int i = 1; i <= n; i++){
			r[i][j] = r[i][j+1];
			if(r[i][j] == 0) r[i][j] = j;
			if(a[i][j] == 1) r[i][j] = 0;
		}
	}
	// for(int i = 1; i <= n; i++){
		// for(int j = 1; j <= n; j++){
			// cout << dn[i][j] <<" ";
		// }
		// // cout << "\n";
	// }
	// return 0;
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int i1 = i; i1 <= n; i1++){
				for(int j1 = j; j1 <= n; j1++){
					int kol = pr[i1][j1] - pr[i1][j-1] - pr[i-1][j1] + pr[i-1][j-1];
					if(kol == 0){
						vector<int> vec , vec2;
						int cur = (i1-i+1)*(j1-j+1);
						for(int J = j; J <= j1; J++) vec.push_back(i-up[i][J]) , vec2.push_back(dn[i1][J]-i1);
						cur += get(vec , vec2);
						vec.clear(); vec2.clear();
						
						for(int I = i; I <= i1; I++) vec.push_back(j-l[I][j]) , vec2.push_back(r[I][j1]-j1);
						cur += get(vec , vec2);
						vec.clear(); vec2.clear();
						ans = max(ans , cur);
					} 
				}
			}
		}
	}
	return ans;
}
int biggest_stadium(int N, vector<vector<int>> F){
	n = N;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			a[i+1][j+1] =  F[i][j];
		}
	}
	return solve();
}
// int main()
// {
    // int N;
    // assert(1 == scanf("%d", &N));
    // std::vector<std::vector<int>> F(N, std::vector<int>(N));
    // for (int i = 0; i < N; i++)
    // {
        // for (int j = 0; j < N; j++)
        // {
            // assert(1 == scanf("%d", &F[i][j]));
        // }
    // }
    // fclose(stdin);
// 
    // int res = biggest_stadium(N, F);
// 
    // printf("%d\n", res);
    // fclose(stdout);
    // return 0;
// }

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