oj.uz

Submission #372636

# Submission time Handle Problem Language Result Execution time Memory
372636 2021-03-01T07:53:38 Z two_sides 코알라 (JOI13_koala) C++17
0 / 100
 55 ms 3948 KB 
/// https://vjudge.net/contest/425052
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 100005;
const ll INF = 0xc0c0c0c0c0c0c0c0;

ll pos[N], str[N], BIT[2][N];

void upd0(int i, ll v) {
    for (; i < N; i += i & -i)
        BIT[0][i] = max(BIT[0][i], v);
}

void upd1(int i, ll v) {
    for (; i > 0; i -= i & -i)
        BIT[1][i] = max(BIT[1][i], v);
}

ll get0(int i) {
    ll res = INF;
    for (; i > 0; i -= i & -i)
        res = max(res, BIT[0][i]);
    return res;
}

ll get1(int i) {
    ll res = INF;
    for (; i < N; i += i & -i)
        res = max(res, BIT[1][i]);
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll k, m, d, a; int n;
    cin >> k >> m >> d >> a >> n;
    vector <int> mods(1, k % d);
    for (int i = 0; i < n; i++) {
        cin >> pos[i] >> str[i];
        mods.push_back(pos[i] % d);
    }
    sort(mods.begin(), mods.end());
    mods.erase(unique(mods.begin(),
    mods.end()), mods.end());
    ll res = -ll(m - k + d - 1) / d * a;
    int id = upper_bound(mods.begin(),
    mods.end(), k % d) - mods.begin();
    memset(BIT, 0xc0, sizeof BIT);
    upd0(id, 0); upd1(id, 0);
    for (int i = 0; i < n; i++) {
        id = upper_bound(mods.begin(),
        mods.end(), pos[i] % d) - mods.begin();
        ll cur = max(get1(id), get0(id) - a);
        cur -= pos[i] / d * a - str[i];
        res = max(res, cur -
        (m - pos[i] + d - 1) / d * a);
        upd0(id, cur + pos[i] / d * a);
        upd1(id, cur + pos[i] / d * a);
    }
    cout << res << '\n';
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1900 KB Output is correct
2 Correct 2 ms 1900 KB Output is correct
3 Incorrect 2 ms 1900 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3948 KB Output is correct
2 Correct 39 ms 3948 KB Output is correct
3 Incorrect 23 ms 3312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3948 KB Output is correct
2 Correct 54 ms 3948 KB Output is correct
3 Correct 52 ms 3948 KB Output is correct
4 Correct 45 ms 3948 KB Output is correct
5 Incorrect 37 ms 3340 KB Output isn't correct
6 Halted 0 ms 0 KB -