Submission #878504

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
878504	2023-11-24T15:29:23 Z	serifefedartar	Kralj (COCI16_kralj)	C++17	140 / 140	343 ms	53376 KB

kralj

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 21;
const ll MAXN = 2e4 + 100;

vector<vector<int>> here;
vector<int> A, DW, EL;

int main() {
	fast
	int n;
	cin >> n;

	here = vector<vector<int>>(n+1, vector<int>());
	A = vector<int>(n+1);
	DW = vector<int>(n+1);
	EL = vector<int>(n+1);
	for (int i = 1; i <= n; i++)
		cin >> A[i];
	for (int i = 1; i <= n; i++)
		cin >> DW[i];
	for (int i = 1; i <= n; i++) {
		cin >> EL[i];
		here[A[i]].push_back(EL[i]);
	}

	pair<int,int> opt = {1e8, 0};
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		cnt += here[i].size();
		opt = min(opt, {cnt - i, i});
	}

	int first_plc = opt.s + 1;
	if (first_plc == n + 1)
		first_plc = 1;

	multiset<int> st;
	cnt = 0;
	for (int i = first_plc; i <= n; i++) {
		for (auto u : here[i])
			st.insert(u);
		auto it = st.lower_bound(DW[i]);
		if (it == st.end())
			st.erase(st.begin());
		else {
			cnt++;
			st.erase(it);
		}
	}
	for (int i = 1; i < first_plc; i++) {
		for (auto u : here[i])
			st.insert(u);
		auto it = st.lower_bound(DW[i]);
		if (it == st.end())
			st.erase(st.begin());
		else {
			cnt++;
			st.erase(it);
		}
	}

	cout << cnt << "\n";
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	343 ms	43360 KB	Output is correct
2	Correct	241 ms	41964 KB	Output is correct
3	Correct	302 ms	52148 KB	Output is correct
4	Correct	321 ms	53376 KB	Output is correct
5	Correct	214 ms	31264 KB	Output is correct
6	Correct	173 ms	31056 KB	Output is correct
7	Correct	274 ms	35700 KB	Output is correct
8	Correct	223 ms	32600 KB	Output is correct
9	Correct	257 ms	37528 KB	Output is correct
10	Correct	212 ms	33940 KB	Output is correct