Submission #852247

#	Time	Username	Problem	Language	Result	Execution time	Memory
852247		denniskim	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	1109 ms	147432 KiB

soccer

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

using namespace std;
typedef int ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 987654321
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n;
ll a[2010][2010];
ll nu[2010][2010];
vector<pll> vec[2010];
map< pair<pll, pll>, ll> dp;

ll sum(ll x1, ll y1, ll x2, ll y2)
{
	return nu[x2][y2] - nu[x1 - 1][y2] - nu[x2][y1 - 1] + nu[x1 - 1][y1 - 1];
}

ll get_top(ll I, ll L, ll R)
{
	ll l = 1, r = I;
	
	while(l <= r)
	{
		ll mid = (l + r) >> 1;
		
		if(!sum(mid, L, I, R))
			r = mid - 1;
		else
			l = mid + 1;
	}
	
	return l;
}

ll get_bottom(ll I, ll L, ll R)
{
	ll l = I, r = n;
	
	while(l <= r)
	{
		ll mid = (l + r) >> 1;
		
		if(!sum(I, L, mid, R))
			l = mid + 1;
		else
			r = mid - 1;
	}
	
	return r;
}

ll f(ll x1, ll y1, ll x2, ll y2)
{
	if(dp.find({{x1, y1}, {x2, y2}}) != dp.end())
		return dp[{{x1, y1}, {x2, y2}}];
	
	ll ret = (x2 - x1 + 1) * (y2 - y1 + 1);
	
	if(x2 < n)
	{
		ll l = 0, r = (ll)vec[x2 + 1].size() - 1;
		
		while(l <= r)
		{
			ll mid = (l + r) >> 1;
			
			if(y1 <= vec[x2 + 1][mid].se)
				r = mid - 1;
			else
				l = mid + 1;
		}
		
		for(ll i = l ; i < (ll)vec[x2 + 1].size() ; i++)
		{
			ll L = max(vec[x2 + 1][i].fi, y1);
			ll R = min(vec[x2 + 1][i].se, y2);
			
			if(L > R)
				break;
			
			ll tp = get_top(x2 + 1, L, R);
			ll bt = get_bottom(x2 + 1, L, R);
			
			ret = max(ret, f(tp, L, bt, R) + (x2 - x1 + 1) * (y2 - y1 - R + L));
		}
	}
	
	if(1 < x1)
	{
		ll l = 0, r = (ll)vec[x1 - 1].size() - 1;
		
		while(l <= r)
		{
			ll mid = (l + r) >> 1;
			
			if(y1 <= vec[x1 - 1][mid].se)
				r = mid - 1;
			else
				l = mid + 1;
		}
		
		for(ll i = l ; i < (ll)vec[x1 - 1].size() ; i++)
		{
			ll L = max(vec[x1 - 1][i].fi, y1);
			ll R = min(vec[x1 - 1][i].se, y2);
			
			if(L > R)
				break;
			
			ll tp = get_top(x1 - 1, L, R);
			ll bt = get_bottom(x1 - 1, L, R);
			
			ret = max(ret, f(tp, L, bt, R) + (x2 - x1 + 1) * (y2 - y1 - R + L));
		}
	}
	
	return dp[{{x1, y1}, {x2, y2}}] = ret;
}

ll biggest_stadium(ll N, vector<vector<ll> > F)
{
	n = N;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		for(ll j = 1 ; j <= n ; j++)
			a[i][j] = F[i - 1][j - 1];
	}
	
	for(ll i = 1 ; i <= n ; i++)
	{
		for(ll j = 1 ; j <= n ; j++)
			nu[i][j] = nu[i - 1][j] + nu[i][j - 1] - nu[i - 1][j - 1] + a[i][j];
	}
	
	for(ll i = 1 ; i <= n ; i++)
	{
		ll st = -1;
		
		for(ll j = 1 ; j <= n ; j++)
		{
			if(st == -1)
			{
				if(!a[i][j])
					st = j;
			}
			
			else
			{
				if(a[i][j])
				{
					vec[i].push_back({st, j - 1});
					st = -1;
				}
			}
		}
		
		if(st != -1)
			vec[i].push_back({st, n});
	}
	
	ll ans = 0;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		for(auto &j : vec[i])
		{
			ll L = j.fi, R = j.se, tp = get_top(i, L, R), bt = get_bottom(i, L, R);
			ans = max(ans, f(tp, L, bt, R));
		}
	}
	
	return ans;
}

• 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: 30 / 30