oj.uz

Submission #839947

# Submission time Handle Problem Language Result Execution time Memory
839947 2023-08-30T21:41:23 Z zscoder Soccer Stadium (IOI23_soccer) C++17
64 / 100
 800 ms 767780 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef bitset<500> b100;

int a[2011][2011];
int dp[511][511][511];
ii iv[2011][2011];
int L[511][511][511];
int R[511][511][511];

int intersect(ii a, ii b)
{
	int l=max(a.fi,b.fi); int r=min(a.se,b.se);
	return max(0,r-l+1);
}

int biggest_stadium(int n, vector<vector<int> > F)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			a[i][j]=F[i][j]; a[i][j]=1-a[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		vector<ii> intervals;
		int st=-1;
		for(int j=0;j<n+1;j++)
		{
			if(a[i][j])
			{
				if(st==-1)
				{
					st=j;
				}
				//else st continues;
			}
			else
			{
				iv[i][j]={-1,-1};
				if(st!=-1)
				{
					intervals.pb({st,j-1});
					for(int k=st;k<j;k++)
					{
						iv[i][k]={st,j-1};
					}
					st=-1;
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			L[i][i][j]=(iv[i][j].fi==-1?int(1e9):iv[i][j].fi);
			R[i][i][j]=iv[i][j].se;
			dp[i][i][j]=max(R[i][i][j]-L[i][i][j]+1,0);
			ans=max(ans,dp[i][i][j]);
			//cerr<<i<<' '<<j<<' '<<L[i][i][j]<<' '<<R[i][i][j]<<' '<<dp[i][i][j]<<'\n';
		}
	}
	
	for(int len=2;len<=n;len++)
	{
		for(int l=0;l+len-1<n;l++)
		{
			int r=l+len-1;
			for(int j=0;j<n;j++)
			{
				int l1 = max(L[l+1][r][j],iv[l][j].fi);
				int l2 = max(L[l][r-1][j],iv[r][j].fi);
				L[l][r][j]=min(l1,l2);
				int r1 = min(R[l+1][r][j],iv[l][j].se);
				int r2 = min(R[l][r-1][j],iv[r][j].se);
				R[l][r][j]=max(r1,r2);
				dp[l][r][j]=max(dp[l+1][r][j]+intersect({L[l+1][r][j],R[l+1][r][j]},{L[l][l][j],R[l][l][j]}),
								dp[l][r-1][j]+intersect({L[l][r-1][j],R[l][r-1][j]},{L[r][r][j],R[r][r][j]}));
				ans=max(ans,dp[l][r][j]);
			}
			//L[l][r][
		}
	}
	return ans;
}
/*
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	
}
*/

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB ok
2 Correct 1 ms 396 KB ok
3 Correct 0 ms 724 KB ok
4 Correct 1 ms 724 KB ok
5 Correct 0 ms 340 KB ok
6 Correct 1 ms 340 KB ok
7 Correct 16 ms 32676 KB ok
8 Correct 800 ms 767720 KB ok
9 Runtime error 321 ms 105892 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB ok
2 Correct 1 ms 340 KB ok
3 Correct 1 ms 396 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 0 ms 340 KB ok
6 Correct 0 ms 340 KB ok
7 Correct 0 ms 340 KB ok
8 Correct 0 ms 340 KB ok
9 Correct 1 ms 340 KB ok
10 Correct 1 ms 360 KB ok
11 Correct 0 ms 340 KB ok
12 Correct 0 ms 340 KB ok
13 Correct 0 ms 340 KB ok
14 Correct 0 ms 340 KB ok
15 Correct 0 ms 596 KB ok
16 Correct 0 ms 596 KB ok
17 Correct 0 ms 596 KB ok
18 Correct 0 ms 596 KB ok
19 Correct 0 ms 596 KB ok
20 Correct 0 ms 596 KB ok
21 Correct 0 ms 596 KB ok
22 Correct 0 ms 596 KB ok
23 Correct 1 ms 596 KB ok
24 Correct 1 ms 540 KB ok
25 Correct 1 ms 596 KB ok
26 Correct 0 ms 596 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB ok
2 Correct 1 ms 340 KB ok
3 Correct 1 ms 396 KB ok
4 Correct 0 ms 724 KB ok
5 Correct 1 ms 724 KB ok
6 Correct 0 ms 340 KB ok
7 Correct 0 ms 340 KB ok
8 Correct 0 ms 340 KB ok
9 Correct 0 ms 340 KB ok
10 Correct 0 ms 340 KB ok
11 Correct 1 ms 340 KB ok
12 Correct 1 ms 360 KB ok
13 Correct 0 ms 340 KB ok
14 Correct 0 ms 340 KB ok
15 Correct 0 ms 340 KB ok
16 Correct 0 ms 340 KB ok
17 Correct 0 ms 596 KB ok
18 Correct 0 ms 596 KB ok
19 Correct 0 ms 596 KB ok
20 Correct 0 ms 596 KB ok
21 Correct 0 ms 596 KB ok
22 Correct 0 ms 596 KB ok
23 Correct 0 ms 596 KB ok
24 Correct 0 ms 596 KB ok
25 Correct 1 ms 596 KB ok
26 Correct 1 ms 540 KB ok
27 Correct 1 ms 596 KB ok
28 Correct 0 ms 596 KB ok
29 Correct 0 ms 596 KB ok
30 Correct 2 ms 3668 KB ok
31 Correct 1 ms 3668 KB ok
32 Correct 2 ms 3576 KB ok
33 Correct 2 ms 3668 KB ok
34 Correct 2 ms 3668 KB ok
35 Correct 2 ms 3668 KB ok
36 Correct 1 ms 3668 KB ok
37 Correct 2 ms 3668 KB ok
38 Correct 1 ms 3668 KB ok
39 Correct 2 ms 3668 KB ok
40 Correct 2 ms 3688 KB ok
41 Correct 2 ms 3668 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB ok
2 Correct 1 ms 340 KB ok
3 Correct 1 ms 396 KB ok
4 Correct 0 ms 724 KB ok
5 Correct 1 ms 724 KB ok
6 Correct 0 ms 340 KB ok
7 Correct 0 ms 340 KB ok
8 Correct 0 ms 340 KB ok
9 Correct 0 ms 340 KB ok
10 Correct 0 ms 340 KB ok
11 Correct 1 ms 340 KB ok
12 Correct 1 ms 360 KB ok
13 Correct 0 ms 340 KB ok
14 Correct 0 ms 340 KB ok
15 Correct 0 ms 340 KB ok
16 Correct 0 ms 340 KB ok
17 Correct 0 ms 596 KB ok
18 Correct 0 ms 596 KB ok
19 Correct 0 ms 596 KB ok
20 Correct 0 ms 596 KB ok
21 Correct 0 ms 596 KB ok
22 Correct 0 ms 596 KB ok
23 Correct 0 ms 596 KB ok
24 Correct 0 ms 596 KB ok
25 Correct 1 ms 596 KB ok
26 Correct 1 ms 540 KB ok
27 Correct 1 ms 596 KB ok
28 Correct 0 ms 596 KB ok
29 Correct 0 ms 596 KB ok
30 Correct 2 ms 3668 KB ok
31 Correct 1 ms 3668 KB ok
32 Correct 2 ms 3576 KB ok
33 Correct 2 ms 3668 KB ok
34 Correct 2 ms 3668 KB ok
35 Correct 2 ms 3668 KB ok
36 Correct 1 ms 3668 KB ok
37 Correct 2 ms 3668 KB ok
38 Correct 1 ms 3668 KB ok
39 Correct 2 ms 3668 KB ok
40 Correct 2 ms 3688 KB ok
41 Correct 2 ms 3668 KB ok
42 Correct 751 ms 767760 KB ok
43 Correct 728 ms 767716 KB ok
44 Correct 779 ms 767740 KB ok
45 Correct 744 ms 767780 KB ok
46 Correct 733 ms 767728 KB ok
47 Correct 751 ms 767696 KB ok
48 Correct 761 ms 767660 KB ok
49 Correct 739 ms 767664 KB ok
50 Correct 736 ms 767692 KB ok
51 Correct 748 ms 767656 KB ok
52 Correct 791 ms 767676 KB ok
53 Correct 757 ms 767740 KB ok
54 Correct 753 ms 767732 KB ok
55 Correct 764 ms 767680 KB ok
56 Correct 748 ms 767736 KB ok
57 Correct 738 ms 767696 KB ok
58 Correct 756 ms 767712 KB ok
59 Correct 756 ms 767700 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB ok
2 Correct 1 ms 340 KB ok
3 Correct 1 ms 396 KB ok
4 Correct 0 ms 724 KB ok
5 Correct 1 ms 724 KB ok
6 Correct 0 ms 340 KB ok
7 Correct 1 ms 340 KB ok
8 Correct 16 ms 32676 KB ok
9 Correct 800 ms 767720 KB ok
10 Runtime error 321 ms 105892 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -