oj.uz

Submission #832391

# Submission time Handle Problem Language Result Execution time Memory
832391 2023-08-21T09:56:13 Z vjudge1 Exam (eJOI20_exam) C++14
39 / 100
 328 ms 99096 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 && pf[val][ri]-pf[val][le-1])ret = max(ret, f(le,ri,val,1));
	
	if(st){// val ada
		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,0,0)<<endl;
		return 0;
	}
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 67684 KB Output is correct
2 Correct 25 ms 67748 KB Output is correct
3 Correct 25 ms 67696 KB Output is correct
4 Correct 26 ms 67736 KB Output is correct
5 Correct 24 ms 67796 KB Output is correct
6 Correct 25 ms 67680 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 17 ms 1564 KB Output is correct
4 Correct 10 ms 1696 KB Output is correct
5 Correct 34 ms 1728 KB Output is correct
6 Correct 12 ms 1656 KB Output is correct
7 Correct 15 ms 1748 KB Output is correct
8 Correct 33 ms 1632 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 98384 KB Output is correct
2 Correct 34 ms 98380 KB Output is correct
3 Correct 65 ms 98656 KB Output is correct
4 Correct 282 ms 99068 KB Output is correct
5 Correct 322 ms 99020 KB Output is correct
6 Correct 328 ms 99096 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 25 ms 67684 KB Output is correct
2 Correct 25 ms 67748 KB Output is correct
3 Correct 25 ms 67696 KB Output is correct
4 Correct 26 ms 67736 KB Output is correct
5 Correct 24 ms 67796 KB Output is correct
6 Correct 25 ms 67680 KB Output is correct
7 Incorrect 26 ms 67720 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 67684 KB Output is correct
2 Correct 25 ms 67748 KB Output is correct
3 Correct 25 ms 67696 KB Output is correct
4 Correct 26 ms 67736 KB Output is correct
5 Correct 24 ms 67796 KB Output is correct
6 Correct 25 ms 67680 KB Output is correct
7 Correct 33 ms 98384 KB Output is correct
8 Correct 34 ms 98380 KB Output is correct
9 Correct 65 ms 98656 KB Output is correct
10 Correct 282 ms 99068 KB Output is correct
11 Correct 322 ms 99020 KB Output is correct
12 Correct 328 ms 99096 KB Output is correct
13 Incorrect 26 ms 67720 KB Output isn't correct
14 Halted 0 ms 0 KB -