Submission #1149261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149261		anmattroi	코알라 (JOI13_koala)	C++17	100 / 100	68 ms	5448 KiB

koala

#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 100005

using namespace std;
using ii = pair<int, int>;


int K, M, D, A, N;

int64_t dp[maxn];

ii a[maxn];

int64_t st[4*maxn];
int b[maxn], n1 = 0;

void upd(int u, int64_t d, int r = 1, int lo = 1, int hi = n1) {
    if (lo == hi) {
        st[r] = max(st[r], d);
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) upd(u, d, r<<1, lo, mid);
    else upd(u, d, r<<1|1, mid+1, hi);
    st[r] = max(st[r<<1], st[r<<1|1]);
}

int64_t get(int u, int v, int r = 1, int lo = 1, int hi = n1) {
    if (u > hi || v < lo) return LLONG_MIN/2;
    if (u <= lo && hi <= v) return st[r];
    int mid = (lo + hi) >> 1;
    return max(get(u, v, r<<1, lo, mid), get(u, v, r<<1|1, mid+1, hi));
}


void update(int pos, int64_t val) {
    int p = lower_bound(b + 1, b + n1 + 1, pos%D) - b;
    upd(p, val);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> K >> M >> D >> A >> N;

    b[++n1] = K%D; b[++n1] = M%D;
    for (int i = 1; i <= N; i++) {
        cin >> a[i].fi >> a[i].se;
        b[++n1] = a[i].fi%D;
    }
    sort(b + 1, b + n1 + 1);
    n1 = unique(b + 1, b + n1 + 1) - b - 1;
    for (int i = 1; i <= 4 * n1; i++) st[i] = LLONG_MIN/2;

    update(K, 1LL*(K/D)*A);

    a[++N] = {M, 0};

    for (int i = 1; i <= N; i++) {
        auto [T, B] = a[i];
        int p = lower_bound(b + 1, b + n1 + 1, T%D) - b;
        dp[i] = max(get(1, p) - A, get(p, n1)) - int64_t(1) * (T/D) * A + B;
        update(T, dp[i] + 1LL * (T/D) * A);
    }
    cout << dp[N];

}

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