Submission #820113

#	Time	Username	Problem	Language	Result	Execution time	Memory
820113		YassirSalama	Exam (eJOI20_exam)	C++17	0 / 100	1081 ms	106136 KiB

exam

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=1e5+100;
const int LOGN=log2(MAXN+100)+1;
int st[MAXN+100][LOGN];
int a[MAXN];
int b[MAXN];
void build(int n){
	for(int i=0;i<n;i++) st[i][0]=a[i];
		for(int j=1;j<LOGN;j++){
			for(int i=0;i+(1<<j)<=n;i++){
				st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			}
	}
}
int query(int l,int r){
	int k=r-l+1;
	int kk=log2(k);
	return max(st[l][kk],st[r-(1<<kk)+1][kk]);
}
map<pair<int,int>,int> mp;
int solve(int i,int last=-1){
	if(i==-1){
		return 0;
	}
	if(mp.find({i,last})!=mp.end()) return mp[{i,last}];
	int ans=0;
	// dbg(i,a[i],b[i],last);
	if(a[i]==b[i]){
		return mp[{i,last}]=1+solve(i-1,a[i]);
	}
	else if(last==b[i]&&a[i]<=last){
		return mp[{i,last}]=max(solve(i-1,a[i]),1+solve(i-1,last));
	}
	else{
		return mp[{i,last}]=max(solve(i-1,last),solve(i-1,a[i]));
	}
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
memset(st,0,sizeof(st));
build(n);
cout<<solve(n-1)<<endl;

}

Compilation message (stderr)

exam.cpp: In function 'long long int solve(long long int, long long int)':
exam.cpp:56:6: warning: unused variable 'ans' [-Wunused-variable]
   56 |  int ans=0;
      |      ^~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22