Submission #1353938

#TimeUsernameProblemLanguageResultExecution timeMemory
1353938sallyBikeparking (EGOI24_bikeparking)C++20
100 / 100
22 ms9348 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    vector<int> S(N), P(N);
    for (int i = 0; i < N; i++) cin >> S[i];
    for (int i = 0; i < N; i++) cin >> P[i];

    int ans = 0;
    
    // Pass 1: 往前停 (+1 分)
    // 我們需要「最近的空位」,所以當我們往右走時,
    // 把有空位的 index 存在一個 stack 裡。
    vector<int> free_slots_idx;
    for (int i = 0; i < N; i++) {
        // 先嘗試讓當前 P[i] 停在左邊的空位
        while (!free_slots_idx.empty() && P[i] > 0) {
            int last_s_idx = free_slots_idx.back();
            int take = min(P[i], S[last_s_idx]);
            
            S[last_s_idx] -= take;
            P[i] -= take;
            ans += take; // 得到 +1 分
            
            if (S[last_s_idx] == 0) {
                free_slots_idx.pop_back();
            }
        }
        // 如果當前 S[i] 還有剩,它變成未來的人可以「往前停」的目標
        if (S[i] > 0) {
            free_slots_idx.push_back(i);
        }
    }

    // Pass 2: 原地停 (0 分)
    // 剩下的 P[i] 嘗試停在剩下的 S[i]
    for (int i = 0; i < N; i++) {
        int take = min(P[i], S[i]);
        P[i] -= take;
        S[i] -= take;
        // 分數不變 (0分)
    }

    // Pass 3: 強迫往後停 (-1 分)
    // 剩下的 P[i] 沒地方去,一定得往後找位子停,每個都是 -1 分
    for (int i = 0; i < N; i++) {
        ans -= P[i]; // 剩下的人每人扣 1 分
    }

    cout << ans << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...