Submission #1181947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181947		mehmetkagan	Discharging (NOI20_discharging)	C++20	47 / 100	1097 ms	51596 KiB

Discharging

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <limits>
using namespace std;
using ll = long long;

const ll INF = 1LL << 60;

// Segment Tree for Range Minimum Query (RMQ)
struct SegTree {
    int n;
    vector<ll> tree;
    
    SegTree(int n_) : n(n_) {
        tree.assign(4*n, INF);
    }
    
    void update(int idx, int l, int r, int pos, ll val) {
        if(l == r) {
            tree[idx] = val;
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid)
            update(2*idx, l, mid, pos, val);
        else
            update(2*idx+1, mid+1, r, pos, val);
        tree[idx] = min(tree[2*idx], tree[2*idx+1]);
    }
    
    ll query(int idx, int l, int r, int ql, int qr) {
        if(ql > r || qr < l) return INF;
        if(ql <= l && r <= qr) return tree[idx];
        int mid = (l + r) / 2;
        return min(query(2*idx, l, mid, ql, qr),
                   query(2*idx+1, mid+1, r, ql, qr));
    }
    
    void update(int pos, ll val) {
        update(1, 0, n-1, pos, val);
    }
    
    ll query(int l, int r) {
        return query(1, 0, n-1, l, r);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    // We use 1-indexing for T and dp for clarity.
    vector<int> T(N+1);
    for (int i = 1; i <= N; i++){
        cin >> T[i];
    }
    
    // Precompute next greater element for indices 1..N.
    // next[i] = smallest j > i with T[j] > T[i], or N+1 if none.
    vector<int> nxt(N+1, N+1);
    stack<int> st;
    for (int i = 1; i <= N; i++){
        while(!st.empty() && T[st.top()] < T[i]){
            nxt[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    // For remaining indices, nxt is already N+1.
    
    // dp[j] = minimal additional cost for customers j+1...N.
    // We want dp[0] = answer.
    // We work with indices 0..N (dp has size N+1)
    vector<ll> dp(N+1, INF);
    dp[N] = 0;
    
    // Build segment tree over dp[0..N].
    // We will update positions as soon as we compute dp[j].
    SegTree seg(N+1);
    // Initialize dp[N] at position N.
    seg.update(N, dp[N]);
    
    // Process j = N-1 downto 0.
    // For a fixed j, we want to consider splitting the interval [j+1, N]
    // into a first segment. Let i be the first index of the segment (i = j+1 initially).
    // Then for i in a segment where the maximum is constant (say = T[i]),
    // candidate cost = (N - j)*T[i] + min_{k in [i, nxt[i]-1]} dp[k].
    for (int j = N-1; j >= 0; j--){
        ll best = INF;
        // i starts at j+1.
        int i = j + 1;
        while(i <= N){
            int r = nxt[i]; // next index where the maximum increases.
            // Query the minimum dp value in the range [i, r-1]
            ll candidate = (ll)(N - j) * T[i] + seg.query(i, r-1);
            best = min(best, candidate);
            i = r;
        }
        dp[j] = best;
        seg.update(j, dp[j]);
    }
    
    cout << dp[0] << "\n";
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 0 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 0 / 28