oj.uz

Submission #57761

# Submission time Handle Problem Language Result Execution time Memory
57761 2018-07-16T02:51:03 Z choikiwon 코알라 (JOI13_koala) C++17
100 / 100
 276 ms 28176 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MN = 100010;

int K, M, D, A, N;
int T[MN], B[MN];

int Xn;
vector<int> X;
map<int, int> dx;

struct BIT {
    vector<ll> tree;
    void init() {
        tree = vector<ll>(4 * MN, -1e18);
    }
    void upd(int idx, ll val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n] = max(tree[n], val);
            return;
        }
        int m = (l + r)>>1;
        upd(idx, val, l, m, 2*n);
        upd(idx, val, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    ll quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return -1e18;
        if(a <= l && r <= b) return tree[n];
        int m = (l + r)>>1;
        ll L = quer(a, b, l, m, 2*n);
        ll R = quer(a, b, m + 1, r, 2*n + 1);
        return max(L, R);
    }
} bit;

ll dp[MN];

int main() {
    scanf("%d %d %d %d %d", &K, &M, &D, &A, &N);
    M -= K;

    T[0] = 0;
    for(int i = 1; i <= N; i++) {
        scanf("%d %d", &T[i], &B[i]);
        T[i] -= K;
    }
    T[++N] = M;

    for(int i = 0; i <= N; i++) {
        X.push_back(T[i] % D);
    }
    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end()) - X.begin());
    Xn = X.size();
    for(int i = 0; i < Xn; i++) dx[X[i]] = i;


    dp[N] = 0;
    bit.init();
    bit.upd(dx[ T[N] % D ], dp[N] + B[N] - 1LL * T[N] / D * A, 0, MN - 1, 1);

    for(int i = N - 1; i >= 0; i--) {
        int r = dx[ T[i] % D ];
        ll t = bit.quer(0, r, 0, MN - 1, 1) + 1LL * T[i] / D * A;
        t = max(t, bit.quer(r + 1, MN - 1, 0, MN - 1, 1) + 1LL * T[i] / D * A - A);
        dp[i] = t;
        bit.upd(r, dp[i] + B[i] - 1LL * T[i] / D * A, 0, MN - 1, 1);
    }

    printf("%lld", dp[0]);
}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d", &K, &M, &D, &A, &N);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &T[i], &B[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3576 KB Output is correct
2 Correct 7 ms 3704 KB Output is correct
3 Correct 7 ms 3720 KB Output is correct
4 Correct 7 ms 3836 KB Output is correct
5 Correct 7 ms 3836 KB Output is correct
6 Correct 8 ms 3892 KB Output is correct
7 Correct 5 ms 3892 KB Output is correct
8 Correct 7 ms 3892 KB Output is correct
9 Correct 8 ms 4072 KB Output is correct
10 Correct 6 ms 4072 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 8156 KB Output is correct
2 Correct 101 ms 9712 KB Output is correct
3 Correct 52 ms 10256 KB Output is correct
4 Correct 84 ms 12864 KB Output is correct
5 Correct 52 ms 13204 KB Output is correct
6 Correct 39 ms 13468 KB Output is correct
7 Correct 66 ms 15656 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 20468 KB Output is correct
2 Correct 270 ms 23864 KB Output is correct
3 Correct 276 ms 26120 KB Output is correct
4 Correct 217 ms 28176 KB Output is correct
5 Correct 128 ms 28176 KB Output is correct
6 Correct 117 ms 28176 KB Output is correct