Submission #361261

#	Time	Username	Problem	Language	Result	Execution time	Memory
361261		RyoPham	코알라 (JOI13_koala)	C++14	50 / 100	74 ms	5484 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

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

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

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

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

lli dp[maxn];

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

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

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

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

    lli get_rev(int x)
    {
        lli res = -inf;
        for(; x < maxn; x += x & -x)
            res = max(res, 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 == 0 ? 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]) * 1LL * A / D + dp[0]);
    for(int i = 1; i <= n + 1; ++i)
    {
        lli t = tree.get(lwb(vals, f[i]));
        dp[i] = t + B[i] - (T[i] + f[i]) * 1LL * A / D;
        t = tree.get_rev(lwb(vals, f[i]) + 1);
        dp[i] = max(dp[i],
                    t + B[i] - (T[i] + f[i] + D) * 1LL * A / D);
        tree.update(lwb(vals, f[i]), (T[i] + f[i]) * 1LL * A / D + dp[i]);
    }
    cout << dp[n + 1] << '\n';
}

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

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