oj.uz

Submission #840869

# Submission time Handle Problem Language Result Execution time Memory
840869 2023-08-31T19:41:34 Z Edu175 Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 896324 KB 
#include "soccer.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) for(auto messi:v)cout<<messi<<" "; cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=2005;

ll n;
ll a[MAXN][MAXN],b[MAXN][MAXN];

ll oper(ll a, ll b){
	return max(a,b);
}
ll K=11;
struct ST{
	vector<vector<ll>>st; ll n;
	//ST(ll n):st(K,vector<ll>(1<<K)),n(n){}
	ST(){}
	void init(vector<ll>a){
		n=SZ(a);
		st.resize(K,vector<ll>(1<<K));
		fore(i,0,n)st[0][i]=a[i];
		fore(k,1,K)fore(i,0,n){
			if(i+(1<<(k-1))>=n)continue;
			st[k][i]=oper(st[k-1][i],st[k-1][i+(1<<(k-1))]);
		}
	}
	ll query(ll s, ll e){
		e++; //askgdsfjsa
		ll k=63-__builtin_clzll(e-s);
		return oper(st[k][s],st[k][e-(1<<k)]);
	}
};
ST qs[2][MAXN];
ll h[2][MAXN][MAXN]; // 0 normal, 1 reversed  left,right

ll rect(ll l, ll r, ll p){
	ll iz=qs[0][p].query(l,r);
	ll dr=n-1-qs[1][n-1-p].query(l,r);
	//cout<<l<<","<<r<<" "<<p<<": "<<iz<<" "<<dr<<": "<<max((ll)0,dr-iz-1)<<"\n";
	//cout<<qs[1][n-1-p].query(l,r)<<"\n";
	//fore(i,0,n)cout<<qs[1][n-1-p].st[0][i]<<" ";
	//cout<<"\n\n";
	return max((ll)0,dr-iz-1);
}

ll dp[MAXN][MAXN];
ll f(ll l, ll r, ll p){
	ll &res=dp[l][r];
	if(res!=-1)return res;
	res=0;
	if(l)res=rect(l-1,r,p)+f(l-1,r,p);
	if(r<n-1)res=max(res,rect(l,r+1,p)+f(l,r+1,p));
	/*if(p==3){
		cout<<l<<","<<r<<": "<<res<<"\n";
	}*/
	return res;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
	n=N;
	fore(i,0,n)fore(j,0,n){
		a[i][j]=F[i][j];
		b[i][n-1-j]=a[i][j];
	}
	mset(h,-1);
	fore(i,0,n){
		h[0][i][0]=(a[i][0]?0:-1);
		h[1][i][0]=(b[i][0]?0:-1);
		fore(j,1,n){
			if(a[i][j])h[0][i][j]=j;
			else h[0][i][j]=h[0][i][j-1];
			
			if(b[i][j])h[1][i][j]=j;
			else h[1][i][j]=h[1][i][j-1];
		}
	}
	/*fore(i,0,n){
		fore(j,0,n)cout<<a[i][j]<<" ";
		cout<<"\n";
	}
	cout<<"\n";
	fore(i,0,n){
		fore(j,0,n)cout<<b[i][j]<<" ";
		cout<<"\n";
	}
	cout<<"\n";
	fore(k,0,2){
		fore(i,0,n){
			fore(j,0,n)cout<<h[k][i][j]<<" ";
			cout<<"\n";
		}
		cout<<"\n";
	}*/
	
	fore(k,0,2)fore(j,0,n){
		vector<ll>v;
		fore(i,0,n)v.pb(h[k][i][j]);
		qs[k][j].init(v);
	}
	ll res=0;
	fore(p,0,n){
		mset(dp,-1);
		fore(i,0,n)res=max(res,f(i+1,i,p));
	}
	return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 95940 KB ok
2 Correct 34 ms 95828 KB ok
3 Correct 49 ms 98088 KB ok
4 Correct 50 ms 98420 KB ok
5 Correct 30 ms 95180 KB ok
6 Correct 33 ms 95848 KB ok
7 Correct 286 ms 131148 KB ok
8 Correct 2215 ms 281580 KB ok
9 Execution timed out 4583 ms 896324 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 95940 KB ok
2 Correct 34 ms 95828 KB ok
3 Correct 33 ms 95820 KB ok
4 Correct 34 ms 95828 KB ok
5 Correct 33 ms 95828 KB ok
6 Correct 34 ms 95900 KB ok
7 Correct 33 ms 95828 KB ok
8 Correct 35 ms 95828 KB ok
9 Correct 40 ms 95892 KB ok
10 Correct 34 ms 95924 KB ok
11 Correct 33 ms 95828 KB ok
12 Correct 33 ms 95820 KB ok
13 Correct 33 ms 95828 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 96596 KB ok
2 Correct 33 ms 95940 KB ok
3 Correct 34 ms 95828 KB ok
4 Correct 33 ms 95820 KB ok
5 Correct 34 ms 95828 KB ok
6 Correct 33 ms 95828 KB ok
7 Correct 34 ms 95900 KB ok
8 Correct 33 ms 95828 KB ok
9 Correct 35 ms 95828 KB ok
10 Correct 40 ms 95892 KB ok
11 Correct 34 ms 95924 KB ok
12 Correct 33 ms 95828 KB ok
13 Correct 33 ms 95820 KB ok
14 Correct 33 ms 95828 KB ok
15 Correct 43 ms 97356 KB ok
16 Correct 44 ms 97364 KB ok
17 Correct 44 ms 97364 KB ok
18 Correct 46 ms 97364 KB ok
19 Correct 42 ms 97364 KB ok
20 Correct 43 ms 97364 KB ok
21 Correct 44 ms 97356 KB ok
22 Correct 43 ms 97364 KB ok
23 Correct 42 ms 97356 KB ok
24 Correct 42 ms 97352 KB ok
25 Correct 46 ms 97296 KB ok
26 Correct 44 ms 97364 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 96596 KB ok
2 Correct 33 ms 95940 KB ok
3 Correct 34 ms 95828 KB ok
4 Correct 49 ms 98088 KB ok
5 Correct 50 ms 98420 KB ok
6 Correct 33 ms 95820 KB ok
7 Correct 34 ms 95828 KB ok
8 Correct 33 ms 95828 KB ok
9 Correct 34 ms 95900 KB ok
10 Correct 33 ms 95828 KB ok
11 Correct 35 ms 95828 KB ok
12 Correct 40 ms 95892 KB ok
13 Correct 34 ms 95924 KB ok
14 Correct 33 ms 95828 KB ok
15 Correct 33 ms 95820 KB ok
16 Correct 33 ms 95828 KB ok
17 Correct 43 ms 97356 KB ok
18 Correct 44 ms 97364 KB ok
19 Correct 44 ms 97364 KB ok
20 Correct 46 ms 97364 KB ok
21 Correct 42 ms 97364 KB ok
22 Correct 43 ms 97364 KB ok
23 Correct 44 ms 97356 KB ok
24 Correct 43 ms 97364 KB ok
25 Correct 42 ms 97356 KB ok
26 Correct 42 ms 97352 KB ok
27 Correct 46 ms 97296 KB ok
28 Correct 44 ms 97364 KB ok
29 Correct 41 ms 97364 KB ok
30 Correct 92 ms 105684 KB ok
31 Correct 101 ms 105836 KB ok
32 Correct 99 ms 105672 KB ok
33 Correct 100 ms 105712 KB ok
34 Correct 101 ms 105704 KB ok
35 Correct 98 ms 105676 KB ok
36 Correct 99 ms 105700 KB ok
37 Correct 106 ms 105648 KB ok
38 Correct 100 ms 105804 KB ok
39 Correct 103 ms 105704 KB ok
40 Correct 101 ms 105720 KB ok
41 Correct 99 ms 105684 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 96596 KB ok
2 Correct 33 ms 95940 KB ok
3 Correct 34 ms 95828 KB ok
4 Correct 49 ms 98088 KB ok
5 Correct 50 ms 98420 KB ok
6 Correct 33 ms 95820 KB ok
7 Correct 34 ms 95828 KB ok
8 Correct 33 ms 95828 KB ok
9 Correct 34 ms 95900 KB ok
10 Correct 33 ms 95828 KB ok
11 Correct 35 ms 95828 KB ok
12 Correct 40 ms 95892 KB ok
13 Correct 34 ms 95924 KB ok
14 Correct 33 ms 95828 KB ok
15 Correct 33 ms 95820 KB ok
16 Correct 33 ms 95828 KB ok
17 Correct 43 ms 97356 KB ok
18 Correct 44 ms 97364 KB ok
19 Correct 44 ms 97364 KB ok
20 Correct 46 ms 97364 KB ok
21 Correct 42 ms 97364 KB ok
22 Correct 43 ms 97364 KB ok
23 Correct 44 ms 97356 KB ok
24 Correct 43 ms 97364 KB ok
25 Correct 42 ms 97356 KB ok
26 Correct 42 ms 97352 KB ok
27 Correct 46 ms 97296 KB ok
28 Correct 44 ms 97364 KB ok
29 Correct 41 ms 97364 KB ok
30 Correct 92 ms 105684 KB ok
31 Correct 101 ms 105836 KB ok
32 Correct 99 ms 105672 KB ok
33 Correct 100 ms 105712 KB ok
34 Correct 101 ms 105704 KB ok
35 Correct 98 ms 105676 KB ok
36 Correct 99 ms 105700 KB ok
37 Correct 106 ms 105648 KB ok
38 Correct 100 ms 105804 KB ok
39 Correct 103 ms 105704 KB ok
40 Correct 101 ms 105720 KB ok
41 Correct 99 ms 105684 KB ok
42 Correct 2243 ms 281580 KB ok
43 Correct 2215 ms 281580 KB ok
44 Correct 2260 ms 281576 KB ok
45 Correct 2225 ms 281580 KB ok
46 Correct 2128 ms 281576 KB ok
47 Correct 2234 ms 281580 KB ok
48 Correct 2224 ms 281576 KB ok
49 Correct 2263 ms 281576 KB ok
50 Correct 2251 ms 281664 KB ok
51 Correct 2244 ms 281580 KB ok
52 Correct 2204 ms 281580 KB ok
53 Correct 2214 ms 281580 KB ok
54 Correct 2220 ms 281676 KB ok
55 Correct 2095 ms 281580 KB ok
56 Correct 2215 ms 281672 KB ok
57 Correct 2227 ms 281584 KB ok
58 Correct 2231 ms 281676 KB ok
59 Correct 2201 ms 281580 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 96596 KB ok
2 Correct 33 ms 95940 KB ok
3 Correct 34 ms 95828 KB ok
4 Correct 49 ms 98088 KB ok
5 Correct 50 ms 98420 KB ok
6 Correct 30 ms 95180 KB ok
7 Correct 33 ms 95848 KB ok
8 Correct 286 ms 131148 KB ok
9 Correct 2215 ms 281580 KB ok
10 Execution timed out 4583 ms 896324 KB Time limit exceeded
11 Halted 0 ms 0 KB -