Submission #1129636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129636		c0det1ger	Bikeparking (EGOI24_bikeparking)	C++20	100 / 100	45 ms	9148 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
 
#define int long long
#define bochi_orz cin.tie(0);cin.sync_with_stdio(0);

signed main() {
    bochi_orz
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++){
        cin >> x[i];
    }
    for (int i = 0; i < n; i++){
        cin >> y[i];
    }
    int sum = 0;
    int net = 0;
    vector<int> vec;
    for (int i = 0; i < n; i++){
        if (vec.size() == 0){
            sum += x[i];
            if (x[i] != 0){
                vec.push_back(i);
            }
            continue;
        }
        while (y[i] > 0 && sum > 0){
            int dec = min(y[i], x[vec.back()]);
            x[vec.back()] -= dec;
            sum -= dec;
            y[i] -= dec;
            net += dec;
            if (x[vec.back()] == 0){
                vec.pop_back();
            }
        }
        sum += x[i];
        if (x[i] != 0){
            vec.push_back(i);
        }
    }
    for (int i = 0; i < n; i++){
        y[i] -= x[i];
        net -= max(y[i], (int)0);
    }
    cout << net << "\n";
}
 
/*
 ____   ___    ___     ____  _____          ____    ____   ___
|      |   |  |   \   |        |     /|    |       |      |   \
|      |   |  |    |  |____    |      |    |   _   |____  |___/
|      |   |  |    |  |        |      |    |    |  |      |  \
|____  |___|  |___/   |____    |    __|__  |____|  |____  |   \
 
*/

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