Submission #241631

#	Time	Username	Problem	Language	Result	Execution time	Memory
241631		AQT	Kralj (COCI16_kralj)	C++14	56 / 140	2091 ms	53264 KiB

kralj

// Problem : COCI '16 Contest 1 #5 Kralj
// Contest : DMOJ
// URL : https://dmoj.ca/problem/coci16c1p5
// Memory Limit : 128 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[500005], apow[500005], bpow[500005];
vector<int> v[500005];

int solve(int s){
	set<int> st;
	int ret = 0;
	for(int i = s, c = 0; c<N; c++, i = (i+1)%N){
		for(int n : v[i]){
			st.insert(n);
		}
		if(st.empty()){
			return 0;
		}
		if(st.lower_bound(apow[i]) != st.end()){
			ret++;
			st.erase(st.lower_bound(apow[i]));
		}
		else{
			st.erase(st.begin());
		}
	}
	//cout << s << "\n";
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 0; i<N; i++){
		cin >> arr[i];
		arr[i]--;
	}
	for(int i = 0; i<N; i++){
		cin >> apow[i];
		//v[arr[i]].push_back(apow[i]);
	}
	for(int i = 0; i<N; i++){
		cin >> bpow[i];
		v[arr[i]].push_back(bpow[i]);
	}
	int ans = 0;
	for(int i = 0; i<N; i++){
		ans = max(ans, solve(i));
	}
	cout << ans << "\n";
}

• Subtask 1: 56 / 140