oj.uz

Submission #542600

# Submission time Handle Problem Language Result Execution time Memory
542600 2022-03-27T05:00:48 Z pokmui9909 코알라 (JOI13_koala) C++17
100 / 100
 147 ms 18812 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12884 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 8 ms 12864 KB Output is correct
4 Correct 8 ms 12860 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 7 ms 12904 KB Output is correct
7 Correct 7 ms 12824 KB Output is correct
8 Correct 7 ms 12884 KB Output is correct
9 Correct 8 ms 12884 KB Output is correct
10 Correct 8 ms 12868 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 18812 KB Output is correct
2 Correct 78 ms 18440 KB Output is correct
3 Correct 34 ms 16652 KB Output is correct
4 Correct 73 ms 18780 KB Output is correct
5 Correct 43 ms 16448 KB Output is correct
6 Correct 30 ms 15188 KB Output is correct
7 Correct 50 ms 17760 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 18772 KB Output is correct
2 Correct 147 ms 18736 KB Output is correct
3 Correct 133 ms 18748 KB Output is correct
4 Correct 114 ms 18752 KB Output is correct
5 Correct 86 ms 16452 KB Output is correct
6 Correct 68 ms 15740 KB Output is correct