제출 #1343261

#제출 시각아이디문제언어결과실행 시간메모리
1343261jmuzhenBikeparking (EGOI24_bikeparking)C++20
100 / 100
33 ms4320 KiB
#include<bits/stdc++.h>
using namespace std;

// #define int long long

#define DEBUG 0
#define printf if(DEBUG) printf

constexpr int MAXN = 3e5+10;

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;cin>>n;
    vector<int> x(n),y(n);
    for(int i = 0; i < n; i++) cin>>x[i];//supply
    for(int i = 0; i < n; i++) cin>>y[i];// demand

    int score = 0;

    stack<pair<int,int>> st; // idx, value of CUSTOMERS.

    for(int i = n-1; i >= 0; i--) {
        while (x[i] > 0 && !st.empty()) {
            auto [j, val] = st.top(); st.pop();
            // y[j] is the customer. not the other way round.
            // so j is the customer.

            int take = min(x[i], y[j]);
            x[i] -= take;
            y[j] -= take;
            score += take;
            if (y[j] > 0) {
                st.push({j, y[j]});
            }
        }

        if (y[i] > 0) {
            st.push({i, y[i]});
        }
    }

    // 2. penalty
    for(int i = n-1; i >= 0; i--) {
        if (y[i] == 0) continue;

        int take = min(y[i], x[i]);
        y[i] -= take;
        x[i] -= take;
        // score += 0 * take.

        if (y[i] > 0) {
            score -= y[i];
            y[i] = 0;
        }

    }

    cout<<score<<endl;

}
#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...