oj.uz

Submission #832418

# Submission time Handle Problem Language Result Execution time Memory
832418 2023-08-21T10:12:33 Z vjudge1 Exam (eJOI20_exam) C++14
39 / 100
 375 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 = 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;
	}
	ret = max({f(le+1,ri,val,st), f(le,ri-1,val,st), 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 67672 KB Output is correct
2 Correct 24 ms 67764 KB Output is correct
3 Correct 25 ms 67724 KB Output is correct
4 Correct 23 ms 67668 KB Output is correct
5 Correct 23 ms 67772 KB Output is correct
6 Correct 23 ms 67708 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 4 ms 724 KB Output is correct
3 Correct 16 ms 1620 KB Output is correct
4 Correct 10 ms 1752 KB Output is correct
5 Correct 33 ms 1652 KB Output is correct
6 Correct 12 ms 1748 KB Output is correct
7 Correct 17 ms 1748 KB Output is correct
8 Correct 34 ms 1660 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 98268 KB Output is correct
2 Correct 37 ms 98384 KB Output is correct
3 Correct 64 ms 98656 KB Output is correct
4 Correct 282 ms 99068 KB Output is correct
5 Correct 375 ms 99092 KB Output is correct
6 Correct 309 ms 99100 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 67672 KB Output is correct
2 Correct 24 ms 67764 KB Output is correct
3 Correct 25 ms 67724 KB Output is correct
4 Correct 23 ms 67668 KB Output is correct
5 Correct 23 ms 67772 KB Output is correct
6 Correct 23 ms 67708 KB Output is correct
7 Incorrect 23 ms 67660 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 67672 KB Output is correct
2 Correct 24 ms 67764 KB Output is correct
3 Correct 25 ms 67724 KB Output is correct
4 Correct 23 ms 67668 KB Output is correct
5 Correct 23 ms 67772 KB Output is correct
6 Correct 23 ms 67708 KB Output is correct
7 Correct 32 ms 98268 KB Output is correct
8 Correct 37 ms 98384 KB Output is correct
9 Correct 64 ms 98656 KB Output is correct
10 Correct 282 ms 99068 KB Output is correct
11 Correct 375 ms 99092 KB Output is correct
12 Correct 309 ms 99100 KB Output is correct
13 Incorrect 23 ms 67660 KB Output isn't correct
14 Halted 0 ms 0 KB -