Submission #361265

#	Time	Username	Problem	Language	Result	Execution time	Memory
361265		RyoPham	코알라 (JOI13_koala)	C++14	100 / 100	96 ms	7912 KiB

koala

#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second
#define double long double
#define int long long

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 1e5 + 5;
const int inf = (int)1e18 + 9;

int K, M, D, A, n;
int T[maxn], B[maxn];

int f[maxn];
vector<int> vals;

int dp[maxn];

struct fenwick
{
    int val[maxn], rev_val[maxn];

    void init()
    {
        fill(begin(val), end(val), -inf);
        fill(begin(rev_val), end(rev_val), -inf);
    }

    void update(int xx, int k)
    {
        for(int x = xx; x < maxn; x += x & -x)
            val[x] = max(val[x], k);
        for(int x = xx; x > 0; x -= x & -x)
            rev_val[x] = max(rev_val[x], k);
    }

    int get(int x)
    {
        int res = -inf;
        for(; x > 0; x -= x & -x)
            res = max(res, val[x]);
        return res;
    }

    int get_rev(int x)
    {
        int res = -inf;
        for(; x < maxn; x += x & -x)
            res = max(res, rev_val[x]);
        return res;
    }
} tree;

void read_input()
{
    cin >> K >> M >> D >> A >> n;
    for(int i = 1; i <= n; ++i)
        cin >> T[i] >> B[i];
    T[0] = K; T[n + 1] = M;
    B[0] = B[n + 1] = 0;
}

void init()
{
    for(int i = 0; i <= n + 1; ++i)
    {
        f[i] = D - T[i] % D;
        vals.push_back(f[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
}

int lwb(const vector<int>&arr, int k)
{
    return lower_bound(arr.begin(), arr.end(), k) - arr.begin() + 1;
}

void solve()
{
    dp[0] = 0;
    tree.update(lwb(vals, f[0]), (T[0] + f[0]) / D * A + dp[0]);
    for(int i = 1; i <= n + 1; ++i)
    {
        int t = tree.get(lwb(vals, f[i]));
        dp[i] = t + B[i] - (T[i] + f[i]) / D * A;
        t = tree.get_rev(lwb(vals, f[i]) + 1);
        dp[i] = max(dp[i],
                    t + B[i] - (T[i] + f[i] + D) / D * A);
        tree.update(lwb(vals, f[i]), (T[i] + f[i]) / D * A + dp[i]);
    }
    cout << dp[n + 1] << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    init();
    solve();
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50