Submission #641810

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
641810	2022-09-17T16:06:47 Z	manizare	Exam (eJOI20_exam)	C++14	88 / 100	231 ms	392172 KB

exam

#include<bits/stdc++.h>
 
#define all(a) a.begin(),a.end()
#define pb push_back
#define int long long
using namespace std ;
 
const int maxn = 5002 , maxq = 1e5+10 , mod = 998244353 ,inf = 1e18 ;
int dp[3][maxn][maxn] , n , a[maxq] , b[maxq] , l[maxq] , r[maxq] , c[maxq] , p[maxq]  ;
stack<int> s , t;
set <int > ff; 
int solve(int n){
	map <int , int > m , q  ;
	int cnt = 1 ;
	for(int i = 1; i <= n ; i++){
		m[a[i]] = cnt ;
		p[cnt] = i ;
		cnt++;
	}
	cnt = 1; 
	vector <int> v , last ;
	last.pb(0);
	for(int i = 1; i <= n ; i++){
		last.pb(inf);
		if(m[b[i]] == 0)continue ;
		int ind = p[m[b[i]]] ;
		if(l[ind] < i && r[ind] > i){
			if(q[b[i]] == 0){
				q[b[i]] = cnt ;
              	cnt++;
            }
			v.pb(m[b[i]]);
		}
	}
	int ans = 0 ;
	for(int i = 0; i < v.size() ; i++){
		int x = upper_bound(all(last) , v[i])- last.begin() - 1;
		last[x+1] = min(last[x+1] , v[i]);
		ans = max(x+1 , ans); 
	}
	return ans ;
}
int solve2(int n){
	int dp[maxq];
	for(int i =1 ; i <= n ; i++){
		if(a[i] != b[1])continue ;
		dp[l[i]+1]++;
		dp[r[i]]--;
	}
	int ans =0  ;
	for(int i =1; i <= n ; i++){
		dp[i] +=dp[i-1] ;
		if(dp[i] !=0 )ans++;
	}
	return ans ;
}


signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >>n ;
	for(int i =1 ; i <= n ; i++){
		cin >> a[i];
	}
	for(int i= 1; i <= n ; i++){
		while(s.size() && a[i] >= a[s.top()])s.pop();
		if(s.size() == 0){
			l[i] = 0 ;
		}else{
			l[i] = s.top();
		}
		s.push(i);
	}
	for(int i = n; i >= 1 ; i--){
		while(t.size() && a[i] >= a[t.top()])t.pop();
		if(t.size() == 0){
			r[i] = n+1 ;
		}else{
			r[i] = t.top();
		}
		t.push(i);
	}
	for(int i = 1; i <= n ; i++){
		cin >> b[i] ;
		ff.insert(b[i]);
	//	cout << l[i] << " " << r[i] <<"<-\n";
	}
	if(ff.size() == 1){
		cout << solve2(n) << "\n";
		return 0 ;
	}
	if(n > 5000){
		cout << solve(n) << "\n" ;
		return 0 ;
	}
	for(int i = 1; i <= n ; i++){
		for(int j =1  ; j <= n ; j++){
			dp[0][i][j] = max(dp[0][i-1][j] , dp[1][i-1][j]);
			dp[1][i][j] = max(max(dp[0][i-1][j-1] , dp[1][i-1][j-1])  , dp[1][i][j-1]) + ((j > l[i] && r[i] > j) && a[i] == b[j]) ;
		}
	}
	for(int i = 1; i <= n ; i++){
		for(int j =1 ; j <= n ; j++){
	//		cout << dp[0][i][j]  << " " << dp[1][i][j] << "       ";
		}
	//	cout << "\n";
	}
	cout << max(dp[0][n][n] , dp[1][n][n]) << "\n";
	return 0 ;
}

Compilation message

exam.cpp: In function 'long long int solve(long long int)':
exam.cpp:36:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i = 0; i < v.size() ; i++){
      |                 ~~^~~~~~~~~~

Subtask #1

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct

Subtask #2

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1108 KB	Output is correct
2	Correct	6 ms	1748 KB	Output is correct
3	Correct	15 ms	4640 KB	Output is correct
4	Incorrect	12 ms	4208 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	4 ms	8276 KB	Output is correct
3	Correct	44 ms	79180 KB	Output is correct
4	Correct	214 ms	376464 KB	Output is correct
5	Correct	228 ms	392172 KB	Output is correct
6	Correct	229 ms	392156 KB	Output is correct

Subtask #4

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1108 KB	Output is correct
2	Correct	42 ms	6248 KB	Output is correct
3	Correct	117 ms	14536 KB	Output is correct
4	Correct	128 ms	14696 KB	Output is correct
5	Correct	162 ms	18272 KB	Output is correct
6	Correct	146 ms	17680 KB	Output is correct
7	Correct	134 ms	16928 KB	Output is correct
8	Correct	109 ms	13964 KB	Output is correct
9	Correct	155 ms	17824 KB	Output is correct
10	Correct	100 ms	18408 KB	Output is correct

Subtask #5

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	596 KB	Output is correct
9	Correct	1 ms	1236 KB	Output is correct
10	Correct	2 ms	2516 KB	Output is correct
11	Correct	2 ms	2516 KB	Output is correct
12	Correct	2 ms	2516 KB	Output is correct
13	Correct	2 ms	2516 KB	Output is correct
14	Correct	1 ms	2516 KB	Output is correct

Subtask #6

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	4 ms	8276 KB	Output is correct
9	Correct	44 ms	79180 KB	Output is correct
10	Correct	214 ms	376464 KB	Output is correct
11	Correct	228 ms	392172 KB	Output is correct
12	Correct	229 ms	392156 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	596 KB	Output is correct
15	Correct	1 ms	1236 KB	Output is correct
16	Correct	2 ms	2516 KB	Output is correct
17	Correct	2 ms	2516 KB	Output is correct
18	Correct	2 ms	2516 KB	Output is correct
19	Correct	2 ms	2516 KB	Output is correct
20	Correct	1 ms	2516 KB	Output is correct
21	Correct	2 ms	2644 KB	Output is correct
22	Correct	14 ms	24148 KB	Output is correct
23	Correct	2 ms	1236 KB	Output is correct
24	Correct	231 ms	392004 KB	Output is correct
25	Correct	229 ms	392012 KB	Output is correct
26	Correct	224 ms	392004 KB	Output is correct
27	Correct	225 ms	392008 KB	Output is correct
28	Correct	225 ms	392140 KB	Output is correct
29	Correct	226 ms	392080 KB	Output is correct
30	Correct	227 ms	392096 KB	Output is correct
31	Correct	222 ms	392100 KB	Output is correct
32	Correct	227 ms	392156 KB	Output is correct