Submission #57761

#	Time	Username	Problem	Language	Result	Execution time	Memory
57761		choikiwon	코알라 (JOI13_koala)	C++17	100 / 100	276 ms	28176 KiB

koala

#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 (stderr)

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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50