Submission #1368232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368232		afric	Bikeparking (EGOI24_bikeparking)	C++20	9 / 100	25 ms	10388 KiB

Main

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> s;
    vector<long long> u;
    vector<int>pos;
    for (int i = 0; i < n; i++) {
        long long x; cin >> x; s.push_back(x);
        if (x > 0) {pos.push_back(i);};
    }
    for (int i = 0; i < n; i++) {
        long long x; cin >> x; u.push_back(x);
    }
    sort(pos.begin(),pos.end(),greater<int>());
    // first pass - go from large to small.
    long long opinion = 0;
    int ptr = 0;
    int rptr = 0;
    int counter = 0;
    
    for (int i = (n-1); i >= 0; i--) {
        if (ptr == pos.size()) {
            while (u[i] > 0) {
                if (s[i] > 0) {
                    if (u[i] > s[i]) {
                        u[i] -= s[i];
                        s[i] = 0;
                    }
                    else {
                        s[i] -= u[i];
                        u[i] = 0;
                    }
                }
                else {
                    while (s[pos[rptr]] == 0) {
                        rptr++;
                    }
                    if (u[i] > s[pos[rptr]]) {
                        u[i] -= s[pos[rptr]];
                        counter -= s[pos[rptr]];
                        s[pos[rptr]] = 0;
                        rptr++;
                    }
                    else {
                        s[pos[rptr]] -= u[i];
                        counter -= u[i];
                        u[i] = 0;
                    }
                }
            }
        }
        else {
            while (u[i] > 0) {
            while (ptr < pos.size() && pos[ptr] >= i) {
                ptr++;
            }
            if (ptr == pos.size()) {
                break;
            }
            if (s[pos[ptr]] > u[i]) {
                counter += u[i];
                u[i] = 0;
                s[pos[ptr]] -= u[i];
            }
            else {
                counter += s[pos[ptr]];
                u[i] -= s[pos[ptr]];
                s[pos[ptr]] = 0;
                ptr++;
            }
        }
        if (ptr == pos.size()) {
            while (u[i] > 0) {
                if (s[i] > 0) {
                    if (u[i] > s[i]) {
                        u[i] -= s[i];
                        s[i] = 0;
                    }
                    else {
                        s[i] -= u[i];
                        u[i] = 0;
                    }
                }
                else {
                    while (s[pos[rptr]] == 0) {
                        rptr--;
                    }
                    if (u[i] > s[pos[rptr]]) {
                        u[i] -= s[pos[rptr]];
                        counter -= s[pos[rptr]];
                        s[pos[rptr]] = 0;
                        rptr++;
                    }
                    else {
                        s[pos[rptr]] -= u[i];
                        counter -= u[i];
                        u[i] = 0;
                    }
                }
            }
        }
        }
    }
    cout << counter << endl;
    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 9 / 9
• Subtask 3: 0 / 19
• Subtask 4: 0 / 24
• Subtask 5: 0 / 32