oj.uz

Submission #832417

# Submission time Handle Problem Language Result Execution time Memory
832417 2023-08-21T10:11:29 Z vjudge1 Exam (eJOI20_exam) C++14
39 / 100
 334 ms 99100 KB 
#include<bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll long long
#define rep(i,n,N) for(int i = n; i<=N; ++i)
#define rap(i,n,N) for(int i = n; i>=N; --i)
#define For(i,n,N) for(int i = n; i< N; ++i)
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define mems(x,y) memset(x,y,sizeof x)
#define ari(x) array<int,x>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fi first
#define se second
const int MAX = 1e5 + 5;
mt19937 rng(time(NULL));

int n,x[MAX],y[MAX],cnt,dp2[5005][5005],dp[205][205][205][2];
vector<int> v,a,b;
bool vis[MAX],gg;
int pf[205][205];

int g(int nw,int val){
	val = max(nw, val);
	if(val>n || nw>n)return 0;
	int &ret = dp2[nw][val];
	if(ret!=-1)return ret;
	return ret = max(g(nw+1,val) + (y[nw]==val), g(nw, val+1));
}

int f(int le,int ri,int val,bool st){
	if(le>ri || val>n)return 0;
	int &ret = dp[le][ri][val][st];
	if(ret!=-1)return ret;
	ret = max({f(le+1,ri,val,st), f(le,ri-1,val,st), f(le,ri,val+1,0)});
	if(!st){
		if(pf[val][ri]-pf[val][le-1])ret = max(ret, f(le,ri,val,1));
		return ret;
	}
//	For(i,le,ri)ret = max(ret, f(le,i,val,st) + f(i+1,ri,val,st));
	
	if(x[le]<=val && y[le]==val)ret = max(ret, f(le+1,ri,val,st) + 1);
	if(x[ri]<=val && y[ri]==val)ret = max(ret, f(le,ri-1,val,st) + 1);
	
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n;
	rep(i,1,n)cin>>x[i], v.pb(x[i]);
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	rep(i,1,n)x[i] = upper_bound(all(v), x[i]) - v.begin();
	auto it = v.begin();
	rep(i,1,n){
		cin>>y[i];
		it = lower_bound(all(v), y[i]);
		y[i] = it==v.end() || *it!=y[i] ? 0 : it-v.begin()+1;
	}
	
//	cout<<"____\n";
//	rep(i,1,n)cout<<x[i]<<" "; cout<<endl;
//	rep(i,1,n)cout<<y[i]<<" "; cout<<endl;
	
	x[0] = x[n+1] = v.size()+1;
	
	bool tc2 = 1;
	rep(i,2,n)if(y[i]!=y[i-1])tc2 = 0;
	if(tc2){
		gg = 0;
		rep(i,1,n){
			if(x[i]==y[i])gg = 1;
			else if(x[i]>y[i])gg = 0;
			vis[i]|= gg;
		}
		gg = 0;
		rap(i,n,1){
			if(x[i]==y[i])gg = 1;
			else if(x[i]>y[i])gg = 0;
			vis[i]|= gg;
			cnt+= vis[i];
		}
		cout<<cnt<<endl;
		return 0;
	}
	
	bool tc3 = 1;
	rep(i,1,n)if(x[i]!=i)tc3 = 0;
	if(tc3){
		mems(dp2, -1);
		cout<<g(1,1)<<endl;
		return 0;
	}
	
	if(n<=200){
		rep(i,1,n){
			rep(j,1,n)pf[j][i] = pf[j][i-1];
			pf[x[i]][i]++;
		}
		mems(dp, -1);
		cout<<f(1,n,1,0)<<endl;
		return 0;
	}
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 67660 KB Output is correct
2 Correct 28 ms 67692 KB Output is correct
3 Correct 24 ms 67676 KB Output is correct
4 Correct 24 ms 67716 KB Output is correct
5 Correct 25 ms 67796 KB Output is correct
6 Correct 23 ms 67784 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 724 KB Output is correct
3 Correct 18 ms 1620 KB Output is correct
4 Correct 10 ms 1748 KB Output is correct
5 Correct 34 ms 1732 KB Output is correct
6 Correct 12 ms 1748 KB Output is correct
7 Correct 15 ms 1736 KB Output is correct
8 Correct 35 ms 1740 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 98252 KB Output is correct
2 Correct 34 ms 98416 KB Output is correct
3 Correct 73 ms 98660 KB Output is correct
4 Correct 293 ms 99072 KB Output is correct
5 Correct 314 ms 99100 KB Output is correct
6 Correct 334 ms 99092 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 67660 KB Output is correct
2 Correct 28 ms 67692 KB Output is correct
3 Correct 24 ms 67676 KB Output is correct
4 Correct 24 ms 67716 KB Output is correct
5 Correct 25 ms 67796 KB Output is correct
6 Correct 23 ms 67784 KB Output is correct
7 Incorrect 22 ms 67768 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 67660 KB Output is correct
2 Correct 28 ms 67692 KB Output is correct
3 Correct 24 ms 67676 KB Output is correct
4 Correct 24 ms 67716 KB Output is correct
5 Correct 25 ms 67796 KB Output is correct
6 Correct 23 ms 67784 KB Output is correct
7 Correct 32 ms 98252 KB Output is correct
8 Correct 34 ms 98416 KB Output is correct
9 Correct 73 ms 98660 KB Output is correct
10 Correct 293 ms 99072 KB Output is correct
11 Correct 314 ms 99100 KB Output is correct
12 Correct 334 ms 99092 KB Output is correct
13 Incorrect 22 ms 67768 KB Output isn't correct
14 Halted 0 ms 0 KB -