Submission #241631

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
241631	2020-06-24T21:12:34 Z	AQT	Kralj (COCI16_kralj)	C++14	56 / 140	2000 ms	53264 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	790 ms	45840 KB	Output is correct
2	Correct	476 ms	44688 KB	Output is correct
3	Correct	564 ms	52456 KB	Output is correct
4	Correct	601 ms	53264 KB	Output is correct
5	Execution timed out	2085 ms	32428 KB	Time limit exceeded
6	Execution timed out	2081 ms	32120 KB	Time limit exceeded
7	Execution timed out	2074 ms	36216 KB	Time limit exceeded
8	Execution timed out	2091 ms	34424 KB	Time limit exceeded
9	Execution timed out	2083 ms	37496 KB	Time limit exceeded
10	Execution timed out	2090 ms	33888 KB	Time limit exceeded