Submission #372656

#	Time	Username	Problem	Language	Result	Execution time	Memory
372656		dung11112003	코알라 (JOI13_koala)	C++11	100 / 100	61 ms	5228 KiB

koala

#include <bits/stdc++.h>

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int maxN = 1e5 + 10;
const ll inf = 1e18;

int n;
ll s, t, D, A, a[maxN], b[maxN], f[maxN], g[maxN], dp[maxN];
vector <ll> vec;

void update(int p, ll d)
{
    for (int x = p; x <= n; x += x & -x)
    {
        uax(f[x], d);
    }
    for (int x = p; x > 0; x &= x - 1)
    {
        uax(g[x], d);
    }
}

ll prefix(int x)
{
    ll ans = -inf;
    for (; x > 0; x &= x - 1)
    {
        uax(ans, f[x]);
    }
    return ans;
}

ll suffix(int x)
{
    ll ans = -inf;
    for (; x <= n; x += x & -x)
    {
        uax(ans, g[x]);
    }
    return ans;
}

ll func(ll x)
{
    return ((x + D - 1) / D) * D - x;
}

namespace judger
{
    ll h[maxN];
    void gen()
    {
        n = rng() % 100 + 1;
        vector <ll> tmp;
        for1(i, n * 3)
        {
            tmp.eb(rng() % 1000);
        }
        sort(all(tmp));
        tmp.resize(unique(all(tmp)) - tmp.begin());
        s = tmp[0];
        for1(i, n)
        {
            a[i] = tmp[i];
            b[i] = rng() % 1000 + 1;
        }
        t = tmp[n + 1];
        A = rng() % 1000 + 1;
        D = rng() % 1000 + 1;
        cerr << s << " " << t << " " << D << " " << A << " " << n << "\n";
        for1(i, n)
        {
            cerr << a[i] << " " << b[i] << "\n";
        }
    }
    void solve()
    {
        for1(i, n)
        {
            ll cur = -(a[i] - s + D - 1) / D * A;
            for1(j, i - 1)
            {
                uax(cur, h[j] - (a[i] - a[j] + D - 1) / D * A);
            }
            h[i] = cur + b[i];
        }
        ll ans = -(t - s + D - 1) / D * A;
        for1(i, n)
        {
            uax(ans, h[i] - (t - a[i] + D - 1) / D * A);
        }
        cout << ans << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
//    freopen(taskname".out", "w", stdout);
    cin >> s >> t >> D >> A >> n;
    for1(i, n)
    {
        cin >> a[i] >> b[i];
    }
//    judger::gen();
//    if (n <= 2e3)
//    {
//        judger::solve();
//        return 0;
//    }
    for1(i, n)
    {
        vec.eb(func(a[i]));
    }
    sort(all(vec));
    fill(f + 1, f + n + 1, -inf);
    fill(g + 1, g + n + 1, -inf);
    for1(i, n)
    {
        int pos = lower_bound(all(vec), func(a[i])) - vec.begin() + 1;
        ll cur = -((a[i] - s + D - 1) / D) * A;
        uax(cur, prefix(pos) - ((a[i] + D - 1) / D) * A);
        uax(cur, suffix(pos + 1) - ((a[i] + D - 1) / D + 1) * A);
        dp[i] = cur + b[i];
        update(pos, dp[i] + ((a[i] + D - 1) / D) * A);
    }
    ll ans = -((t - s + D - 1) / D) * A;
    for1(i, n)
    {
        uax(ans, dp[i] - ((t - a[i] + D - 1) / D) * A);
    }
    cout << ans;
    return 0;
}

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