oj.uz

Submission #372630

# Submission time Handle Problem Language Result Execution time Memory
372630 2021-03-01T07:33:46 Z ngpin04 코알라 (JOI13_koala) C++14
100 / 100
 118 ms 7532 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 4332 KB Output is correct
2 Correct 47 ms 4076 KB Output is correct
3 Correct 19 ms 2928 KB Output is correct
4 Correct 46 ms 4332 KB Output is correct
5 Correct 27 ms 2800 KB Output is correct
6 Correct 17 ms 1904 KB Output is correct
7 Correct 24 ms 3436 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 6380 KB Output is correct
2 Correct 118 ms 7404 KB Output is correct
3 Correct 110 ms 7532 KB Output is correct
4 Correct 92 ms 7532 KB Output is correct
5 Correct 67 ms 4720 KB Output is correct
6 Correct 50 ms 3568 KB Output is correct