oj.uz

Submission #361261

# Submission time Handle Problem Language Result Execution time Memory
361261 2021-01-29T02:10:52 Z RyoPham 코알라 (JOI13_koala) C++14
50 / 100
 74 ms 5484 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4844 KB Output is correct
2 Correct 44 ms 4460 KB Output is correct
3 Correct 28 ms 3312 KB Output is correct
4 Correct 43 ms 4844 KB Output is correct
5 Correct 26 ms 3056 KB Output is correct
6 Correct 16 ms 2032 KB Output is correct
7 Correct 31 ms 3820 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 5228 KB Output is correct
2 Incorrect 72 ms 5484 KB Output isn't correct
3 Halted 0 ms 0 KB -