Submission #260775

#	Time	Username	Problem	Language	Result	Execution time	Memory
260775		thecodingwizard	Kralj (COCI16_kralj)	C++11	140 / 140	762 ms	51048 KiB

kralj

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);

    int n; cin >> n;
    vector<int> adversaries[n];
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        adversaries[x-1].push_back(i);
    }
    int D[n], E[n];
    for (int i = 0; i < n; i++) cin >> D[i];
    for (int i = 0; i < n; i++) cin >> E[i];

    int ctr = 0;
    for (int i = 0; i < n; i++) {
        ctr = max(0, ctr - 1 + (int)adversaries[i].size());
    }
    int startIdx = -1;
    for (int i = 0; i < n; i++) {
        if (ctr == 0) {
            startIdx = i;
            break;
        }
        ctr = ctr - 1 + (int)adversaries[i].size();
        assert(ctr >= 0);
    }

    multiset<int> elves;
    int ans = 0;

    for (int i = 0; i < n; i++) {
        int idx = (startIdx + i) % n;
        for (int elf : adversaries[idx]) {
            elves.insert(E[elf]);
        }
        auto it = elves.upper_bound(D[idx]);
        if (it == elves.end()) {
            elves.erase(elves.begin());
        } else {
            elves.erase(it);
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

• Subtask 1: 140 / 140