제출 #372630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
372630		ngpin04	코알라 (JOI13_koala)	C++14	100 / 100	118 ms	7532 KiB

koala

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
const long long oo = 1e18;

struct segtree {
    int n;
    vector <long long> st;

    segtree(int _n) {
        n = _n;
        st.assign(4 * n, -oo);
    }

    void update(int id, int l, int r, int pos, long long val) {
        if (l > pos || r < pos)
            return;
        if (l == r) {
            st[id] = max(st[id], val);
            return;
        }

        int mid = (l + r) >> 1;
        update(id << 1, l, mid, pos, val);
        update(id << 1 | 1, mid + 1, r, pos, val);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }

    void update(int pos, long long val) {
        update(1, 1, n, pos, val);
    }

    long long getmax(int id, int l, int r, int u, int v) {
        if (l > v || r < u)
            return -oo;
        if (l >= u && r <= v)
            return st[id];
        int mid = (l + r) >> 1;
        long long lnode = getmax(id << 1, l, mid, u, v);
        long long rnode = getmax(id << 1 | 1, mid + 1, r, u, v);
        return max(lnode, rnode);
    }

    long long getmax(int l, int r) {
        return getmax(1, 1, n, l, r);
    }
};

vector <int> val;

long long dp[N];

int a[N];
int b[N];
int n,d,m,k,x;

int getpos(int x) {
    return lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
}

void solve() {
    segtree st(val.size());

    for (int i = 0; i <= n; i++) {
        int pos = getpos(a[i] % d);
        if (i == 0) {
            st.update(pos, (long long) (a[0] / d) * x);
            continue;
        }

        dp[i] = st.getmax(pos, val.size()) - (long long) (a[i] / d) * x;
        if (pos > 1)
            dp[i] = max(dp[i], st.getmax(1, pos - 1) - (long long) (a[i] / d + 1) * x);

        dp[i] += b[i];
        st.update(pos, dp[i] + (long long) (a[i] / d) * x);
    }
    cout << dp[n] << "\n";
}

void bruteforce() {
    for (int i = 1; i <= n; i++) {
        dp[i] = -oo;
        for (int j = 0; j < i; j++) {
            dp[i] = max(dp[i], dp[j] - (long long) (a[i] - a[j] + d - 1) / d * x);
        }
        dp[i] += b[i];
    }
    cout << dp[n];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    cin >> k >> m >> d >> x >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    a[0] = k;
    a[++n] = m;

    for (int i = 0; i <= n; i++) {
        val.push_back(a[i] % d);
    }

    sort(val.begin(), val.end());

    val.resize(unique(val.begin(), val.end()) - val.begin());

    //bruteforce();
    solve();


    return 0;
}

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