Submission #810596

#	Time	Username	Problem	Language	Result	Execution time	Memory
810596		vjudge1	코알라 (JOI13_koala)	C++17	100 / 100	87 ms	10980 KiB

koala

#include <bits/stdc++.h>
#define ll long long
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) ((1LL) << (i))

using namespace std;
const long mod = 1e9+7;
const long Nmax = 1e5+7;

int fr, to, cost, d, n;
int t[Nmax], b[Nmax];
ll dp[Nmax], inf;

vector<int> nen, num;
pair<ll, int> st[Nmax * 4];

pair<ll, int> maximize(pair<ll, int> left, pair<ll, int> right)
{
    if (left.first > right.first) return left;
    else return right;
}

void update(int id, int l, int r, int i, ll v, int k)
{
    if (l > i || r < i) return;
    if (l == r)
    {
        st[id] = maximize(st[id], {v, k});
//        cout << st[id].first << " ";
        return;
    }
    int mid = (l + r) >> 1;
    update(id * 2, l, mid, i, v, k);
    update(id * 2 + 1, mid + 1, r, i, v, k);
    st[id] = maximize(st[id * 2], st[id * 2 + 1]);
}

pair<ll, int> get(int id, int l, int r, int u, int v)
{
    if (l > v || r < u) return {-inf, -1};
    if (l >= u && r <= v) return st[id];
    int mid = (l + r) >> 1;
    return maximize(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("name.inp","r",stdin);
    //freopen("name.out","w",stdout);
    cin >> fr >> to >> d >> cost >> n;
    n += 2;
    t[1] = fr;
    t[n] = to;
    nen.push_back(fr % d);
    nen.push_back(to % d);
    for (int i = 2; i <= n - 1; i++)
    {
        cin >> t[i] >> b[i];
        nen.push_back(t[i] % d);
    }

    sort(nen.begin(), nen.end());
    num.push_back(nen[0]);
    for (int i = 1; i < nen.size(); i++) if (nen[i] != nen[i - 1]) num.push_back(nen[i]);

//    for (int i = 0; i < num.size(); i++) cout << num[i] << " ";
//    cout << "\n";

    memset(dp, -0x3f, sizeof dp);
    for (int i = 1; i < 4 * Nmax; i++) st[i] = {dp[0], -1};
    inf = -dp[0];
    inf += 5;
//    cout << inf << "\n";;
    dp[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i == 1)
        {
            int modun = t[i] % d;
            int pos = lower_bound(num.begin(), num.end(), modun) - num.begin() + 1;
//            cout << pos << " ";
            update(1, 1, num.size(), pos, dp[i] + 1LL * t[i]/d * cost, i);
        }
        else
        {
            int modun = t[i] % d;
//            cout << modun << " ";
            int pos = lower_bound(num.begin(), num.end(), modun) - num.begin() + 1;
            int j = get(1, 1, num.size(), 1, pos - 1).second;
//            cout << i << " " << j << ".";
            if (j != -1) dp[i] = max(dp[i], dp[j] - 1LL * (t[i]/d - t[j]/d + 1) * cost + b[i]);

            j = get(1, 1, num.size(), pos, num.size()).second;
//            cout << i << " " << j << "\n";
            if (j != -1) dp[i] = max(dp[i], dp[j] - 1LL * (t[i]/d - t[j]/d) * cost + b[i]);
            update(1, 1, num.size(), pos, dp[i] + 1LL * t[i]/d * cost, i);
        }
    }
//    cout << "\n";
//    for (int i = 1; i <= n; i++) cout << dp[i] << " ";
//    cout << "\n";
    cout << dp[n];
}

Compilation message (stderr)

koala.cpp: In function 'int main()':
koala.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 1; i < nen.size(); i++) if (nen[i] != nen[i - 1]) num.push_back(nen[i]);
      |                     ~~^~~~~~~~~~~~

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