oj.uz

Submission #840722

# Submission time Handle Problem Language Result Execution time Memory
840722 2023-08-31T16:14:29 Z Edu175 Soccer Stadium (IOI23_soccer) C++17
0 / 100
 44 ms 98004 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)>=n)continue;
			st[k][i]=oper(st[k-1][i],st[k-1][i+(1<<k)]);
		}
	}
	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 izq=p-qs[0][p].query(l,r);
	ll der=n-1-p-qs[1][n-1-p].query(l,r);
	return izq+der;
}

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=rect(l,r+1,p)+f(l,r+1,p);
	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){
		fore(k,0,2)h[k][i][0]=(a[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 37 ms 96584 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 95828 KB ok
2 Correct 33 ms 95828 KB ok
3 Incorrect 44 ms 98004 KB wrong
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 95828 KB ok
2 Correct 33 ms 95828 KB ok
3 Correct 33 ms 95828 KB ok
4 Partially correct 33 ms 95828 KB partial
5 Incorrect 35 ms 95820 KB wrong
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 96584 KB ok
2 Correct 32 ms 95828 KB ok
3 Correct 33 ms 95828 KB ok
4 Correct 33 ms 95828 KB ok
5 Partially correct 33 ms 95828 KB partial
6 Incorrect 35 ms 95820 KB wrong
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 96584 KB ok
2 Correct 32 ms 95828 KB ok
3 Correct 33 ms 95828 KB ok
4 Incorrect 44 ms 98004 KB wrong
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 96584 KB ok
2 Correct 32 ms 95828 KB ok
3 Correct 33 ms 95828 KB ok
4 Incorrect 44 ms 98004 KB wrong
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 96584 KB ok
2 Correct 32 ms 95828 KB ok
3 Correct 33 ms 95828 KB ok
4 Incorrect 44 ms 98004 KB wrong
5 Halted 0 ms 0 KB -