oj.uz

Submission #852247

# Submission time Handle Problem Language Result Execution time Memory
852247 2023-09-21T13:31:30 Z denniskim Soccer Stadium (IOI23_soccer) C++17
100 / 100
 1109 ms 147432 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2400 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 0 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2392 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 2 ms 4952 KB ok
8 Correct 19 ms 11612 KB ok
9 Correct 292 ms 64336 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 0 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2648 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 2396 KB ok
8 Correct 1 ms 2392 KB ok
9 Correct 1 ms 2396 KB ok
10 Correct 1 ms 2396 KB ok
11 Correct 1 ms 2396 KB ok
12 Correct 1 ms 2396 KB ok
13 Correct 1 ms 2396 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2400 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2648 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 2396 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 1 ms 2392 KB ok
10 Correct 1 ms 2396 KB ok
11 Correct 1 ms 2396 KB ok
12 Correct 1 ms 2396 KB ok
13 Correct 1 ms 2396 KB ok
14 Correct 1 ms 2396 KB ok
15 Correct 1 ms 2412 KB ok
16 Correct 1 ms 2436 KB ok
17 Correct 1 ms 2396 KB ok
18 Correct 1 ms 2396 KB ok
19 Correct 1 ms 2392 KB ok
20 Correct 1 ms 2392 KB ok
21 Correct 1 ms 2396 KB ok
22 Correct 1 ms 2396 KB ok
23 Correct 1 ms 2540 KB ok
24 Correct 1 ms 2396 KB ok
25 Correct 1 ms 2396 KB ok
26 Correct 1 ms 2396 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2400 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 2648 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 1 ms 2396 KB ok
10 Correct 1 ms 2396 KB ok
11 Correct 1 ms 2392 KB ok
12 Correct 1 ms 2396 KB ok
13 Correct 1 ms 2396 KB ok
14 Correct 1 ms 2396 KB ok
15 Correct 1 ms 2396 KB ok
16 Correct 1 ms 2396 KB ok
17 Correct 1 ms 2412 KB ok
18 Correct 1 ms 2436 KB ok
19 Correct 1 ms 2396 KB ok
20 Correct 1 ms 2396 KB ok
21 Correct 1 ms 2392 KB ok
22 Correct 1 ms 2392 KB ok
23 Correct 1 ms 2396 KB ok
24 Correct 1 ms 2396 KB ok
25 Correct 1 ms 2540 KB ok
26 Correct 1 ms 2396 KB ok
27 Correct 1 ms 2396 KB ok
28 Correct 1 ms 2396 KB ok
29 Correct 1 ms 2396 KB ok
30 Correct 1 ms 2652 KB ok
31 Correct 1 ms 2652 KB ok
32 Correct 1 ms 2652 KB ok
33 Correct 1 ms 2652 KB ok
34 Correct 1 ms 2652 KB ok
35 Correct 1 ms 2652 KB ok
36 Correct 1 ms 2652 KB ok
37 Correct 1 ms 2652 KB ok
38 Correct 1 ms 2652 KB ok
39 Correct 1 ms 2652 KB ok
40 Correct 1 ms 2652 KB ok
41 Correct 1 ms 2652 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2400 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 2648 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 1 ms 2396 KB ok
10 Correct 1 ms 2396 KB ok
11 Correct 1 ms 2392 KB ok
12 Correct 1 ms 2396 KB ok
13 Correct 1 ms 2396 KB ok
14 Correct 1 ms 2396 KB ok
15 Correct 1 ms 2396 KB ok
16 Correct 1 ms 2396 KB ok
17 Correct 1 ms 2412 KB ok
18 Correct 1 ms 2436 KB ok
19 Correct 1 ms 2396 KB ok
20 Correct 1 ms 2396 KB ok
21 Correct 1 ms 2392 KB ok
22 Correct 1 ms 2392 KB ok
23 Correct 1 ms 2396 KB ok
24 Correct 1 ms 2396 KB ok
25 Correct 1 ms 2540 KB ok
26 Correct 1 ms 2396 KB ok
27 Correct 1 ms 2396 KB ok
28 Correct 1 ms 2396 KB ok
29 Correct 1 ms 2396 KB ok
30 Correct 1 ms 2652 KB ok
31 Correct 1 ms 2652 KB ok
32 Correct 1 ms 2652 KB ok
33 Correct 1 ms 2652 KB ok
34 Correct 1 ms 2652 KB ok
35 Correct 1 ms 2652 KB ok
36 Correct 1 ms 2652 KB ok
37 Correct 1 ms 2652 KB ok
38 Correct 1 ms 2652 KB ok
39 Correct 1 ms 2652 KB ok
40 Correct 1 ms 2652 KB ok
41 Correct 1 ms 2652 KB ok
42 Correct 65 ms 14932 KB ok
43 Correct 70 ms 15952 KB ok
44 Correct 32 ms 12372 KB ok
45 Correct 28 ms 12124 KB ok
46 Correct 53 ms 13736 KB ok
47 Correct 19 ms 11608 KB ok
48 Correct 18 ms 11612 KB ok
49 Correct 18 ms 11476 KB ok
50 Correct 39 ms 12184 KB ok
51 Correct 26 ms 12760 KB ok
52 Correct 19 ms 11472 KB ok
53 Correct 22 ms 11600 KB ok
54 Correct 19 ms 11612 KB ok
55 Correct 19 ms 11480 KB ok
56 Correct 18 ms 11612 KB ok
57 Correct 46 ms 15696 KB ok
58 Correct 49 ms 15956 KB ok
59 Correct 53 ms 16724 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2400 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 2392 KB ok
7 Correct 1 ms 2396 KB ok
8 Correct 2 ms 4952 KB ok
9 Correct 19 ms 11612 KB ok
10 Correct 292 ms 64336 KB ok
11 Correct 1 ms 2396 KB ok
12 Correct 1 ms 2648 KB ok
13 Correct 1 ms 2396 KB ok
14 Correct 1 ms 2396 KB ok
15 Correct 1 ms 2396 KB ok
16 Correct 1 ms 2392 KB ok
17 Correct 1 ms 2396 KB ok
18 Correct 1 ms 2396 KB ok
19 Correct 1 ms 2396 KB ok
20 Correct 1 ms 2396 KB ok
21 Correct 1 ms 2396 KB ok
22 Correct 1 ms 2412 KB ok
23 Correct 1 ms 2436 KB ok
24 Correct 1 ms 2396 KB ok
25 Correct 1 ms 2396 KB ok
26 Correct 1 ms 2392 KB ok
27 Correct 1 ms 2392 KB ok
28 Correct 1 ms 2396 KB ok
29 Correct 1 ms 2396 KB ok
30 Correct 1 ms 2540 KB ok
31 Correct 1 ms 2396 KB ok
32 Correct 1 ms 2396 KB ok
33 Correct 1 ms 2396 KB ok
34 Correct 1 ms 2396 KB ok
35 Correct 1 ms 2652 KB ok
36 Correct 1 ms 2652 KB ok
37 Correct 1 ms 2652 KB ok
38 Correct 1 ms 2652 KB ok
39 Correct 1 ms 2652 KB ok
40 Correct 1 ms 2652 KB ok
41 Correct 1 ms 2652 KB ok
42 Correct 1 ms 2652 KB ok
43 Correct 1 ms 2652 KB ok
44 Correct 1 ms 2652 KB ok
45 Correct 1 ms 2652 KB ok
46 Correct 1 ms 2652 KB ok
47 Correct 65 ms 14932 KB ok
48 Correct 70 ms 15952 KB ok
49 Correct 32 ms 12372 KB ok
50 Correct 28 ms 12124 KB ok
51 Correct 53 ms 13736 KB ok
52 Correct 19 ms 11608 KB ok
53 Correct 18 ms 11612 KB ok
54 Correct 18 ms 11476 KB ok
55 Correct 39 ms 12184 KB ok
56 Correct 26 ms 12760 KB ok
57 Correct 19 ms 11472 KB ok
58 Correct 22 ms 11600 KB ok
59 Correct 19 ms 11612 KB ok
60 Correct 19 ms 11480 KB ok
61 Correct 18 ms 11612 KB ok
62 Correct 46 ms 15696 KB ok
63 Correct 49 ms 15956 KB ok
64 Correct 53 ms 16724 KB ok
65 Correct 1109 ms 118248 KB ok
66 Correct 632 ms 118868 KB ok
67 Correct 459 ms 88408 KB ok
68 Correct 349 ms 66216 KB ok
69 Correct 553 ms 77916 KB ok
70 Correct 731 ms 88400 KB ok
71 Correct 294 ms 64848 KB ok
72 Correct 256 ms 63312 KB ok
73 Correct 267 ms 63568 KB ok
74 Correct 257 ms 63460 KB ok
75 Correct 261 ms 63568 KB ok
76 Correct 680 ms 71660 KB ok
77 Correct 682 ms 71504 KB ok
78 Correct 340 ms 75212 KB ok
79 Correct 328 ms 68452 KB ok
80 Correct 298 ms 66904 KB ok
81 Correct 304 ms 66900 KB ok
82 Correct 346 ms 70680 KB ok
83 Correct 486 ms 85712 KB ok
84 Correct 270 ms 63572 KB ok
85 Correct 262 ms 63316 KB ok
86 Correct 268 ms 63568 KB ok
87 Correct 281 ms 64336 KB ok
88 Correct 260 ms 63572 KB ok
89 Correct 255 ms 63568 KB ok
90 Correct 261 ms 63564 KB ok
91 Correct 261 ms 63568 KB ok
92 Correct 352 ms 77008 KB ok
93 Correct 391 ms 79952 KB ok
94 Correct 302 ms 68692 KB ok
95 Correct 279 ms 66384 KB ok
96 Correct 273 ms 65360 KB ok
97 Correct 268 ms 64856 KB ok
98 Correct 271 ms 64076 KB ok
99 Correct 932 ms 130572 KB ok
100 Correct 771 ms 126540 KB ok
101 Correct 738 ms 120400 KB ok
102 Correct 785 ms 126560 KB ok
103 Correct 863 ms 137124 KB ok
104 Correct 911 ms 142240 KB ok
105 Correct 943 ms 143960 KB ok
106 Correct 949 ms 147432 KB ok
107 Correct 968 ms 146384 KB ok
108 Correct 394 ms 73816 KB ok
109 Correct 408 ms 73804 KB ok