oj.uz

Submission #361265

# Submission time Handle Problem Language Result Execution time Memory
361265 2021-01-29T02:33:57 Z RyoPham 코알라 (JOI13_koala) C++14
100 / 100
 96 ms 7912 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
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 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 512 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 512 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 4584 KB Output is correct
2 Correct 44 ms 4584 KB Output is correct
3 Correct 26 ms 3180 KB Output is correct
4 Correct 50 ms 4496 KB Output is correct
5 Correct 26 ms 2924 KB Output is correct
6 Correct 16 ms 2156 KB Output is correct
7 Correct 29 ms 4584 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 5480 KB Output is correct
2 Correct 96 ms 6120 KB Output is correct
3 Correct 69 ms 7912 KB Output is correct
4 Correct 60 ms 7912 KB Output is correct
5 Correct 48 ms 5100 KB Output is correct
6 Correct 39 ms 3948 KB Output is correct