제출 #542600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542600		pokmui9909	코알라 (JOI13_koala)	C++17	100 / 100	147 ms	18812 KiB

koala

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

ll K, M, D, A, N;
ll T[100005], B[100005];
ll dp[100005];
struct SegTree{
    ll T[1600005] = {};
    SegTree() {fill(T, T + 1600005, -1e18);}
    void update(ll n, ll s, ll e, ll k, ll v){
        if(s == e){
            T[n] = max(T[n], v);
            return;
        }
        ll m = (s + e) / 2;
        if(k <= m) update(2 * n, s, m, k, v);
        else update(2 * n + 1, m + 1, e, k, v);
        T[n] = max(T[n * 2], T[n * 2 + 1]);
    }
    ll query(ll n, ll s, ll e, ll l, ll r){
        if(e < l || s > r || l > r) return -1e18;
        if(l <= s && e <= r) return T[n];
        ll m = (s + e) / 2;
        return max(query(n * 2, s, m, l, r), query(n * 2 + 1, m + 1, e, l, r));
    }
}ST;
vector<ll> V;
ll get_idx(ll k){
    return lower_bound(V.begin(), V.end(), k) - V.begin();
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> K >> M >> D >> A >> N; N += 2;
    T[1] = K, T[N] = M;
    for(int i = 2; i <= N - 1; i++){
        cin >> T[i] >> B[i];
        V.push_back(T[i] % D);
        V.push_back(T[i] % D - 1);
    }
    V.push_back(0);
    V.push_back(T[1] % D);
    V.push_back(T[N] % D);
    V.push_back(T[N] % D - 1);
    V.push_back(D - 1);
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());
    ST.update(1, 0, 4 * N, get_idx(T[1] % D), A * (T[1] / D));
    for(int i = 2; i <= N; i++){
        dp[i] = -1e18;
        dp[i] = max(dp[i], ST.query(1, 0, 4 * N, get_idx(0), get_idx(T[i] % D - 1)) - A);
        dp[i] = max(dp[i], ST.query(1, 0, 4 * N, get_idx(T[i] % D), get_idx(D - 1)));
        dp[i] += B[i] - A * (T[i] / D);
        ST.update(1, 0, 4 * N, get_idx(T[i] % D), dp[i] + A * (T[i] / D));
    }
    cout << dp[N];
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50