oj.uz

Submission #820113

# Submission time Handle Problem Language Result Execution time Memory
820113 2023-08-10T19:36:14 Z YassirSalama Exam (eJOI20_exam) C++17
0 / 100
 1000 ms 106136 KB 
#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

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.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 106136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

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

Subtask #6
0 / 22.0

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