oj.uz

Submission #832403

# Submission time Handle Problem Language Result Execution time Memory
832403 2023-08-21T10:02:42 Z vjudge1 Exam (eJOI20_exam) C++14
39 / 100
 317 ms 99136 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,1,0)<<endl;
		return 0;
	}
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 67668 KB Output is correct
2 Correct 27 ms 67716 KB Output is correct
3 Correct 23 ms 67668 KB Output is correct
4 Correct 23 ms 67800 KB Output is correct
5 Correct 24 ms 67772 KB Output is correct
6 Correct 28 ms 67696 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 17 ms 1584 KB Output is correct
4 Correct 10 ms 1748 KB Output is correct
5 Correct 35 ms 1708 KB Output is correct
6 Correct 15 ms 1748 KB Output is correct
7 Correct 15 ms 1708 KB Output is correct
8 Correct 33 ms 1700 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 98356 KB Output is correct
2 Correct 35 ms 98340 KB Output is correct
3 Correct 70 ms 98556 KB Output is correct
4 Correct 287 ms 99096 KB Output is correct
5 Correct 315 ms 99092 KB Output is correct
6 Correct 317 ms 99136 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 28 ms 67668 KB Output is correct
2 Correct 27 ms 67716 KB Output is correct
3 Correct 23 ms 67668 KB Output is correct
4 Correct 23 ms 67800 KB Output is correct
5 Correct 24 ms 67772 KB Output is correct
6 Correct 28 ms 67696 KB Output is correct
7 Incorrect 23 ms 67784 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 67668 KB Output is correct
2 Correct 27 ms 67716 KB Output is correct
3 Correct 23 ms 67668 KB Output is correct
4 Correct 23 ms 67800 KB Output is correct
5 Correct 24 ms 67772 KB Output is correct
6 Correct 28 ms 67696 KB Output is correct
7 Correct 33 ms 98356 KB Output is correct
8 Correct 35 ms 98340 KB Output is correct
9 Correct 70 ms 98556 KB Output is correct
10 Correct 287 ms 99096 KB Output is correct
11 Correct 315 ms 99092 KB Output is correct
12 Correct 317 ms 99136 KB Output is correct
13 Incorrect 23 ms 67784 KB Output isn't correct
14 Halted 0 ms 0 KB -