oj.uz

Submission #405679

# Submission time Handle Problem Language Result Execution time Memory
405679 2021-05-16T17:26:33 Z Aldas25 Salesman (IOI09_salesman) C++14
100 / 100
 2102 ms 48160 KB 
#pragma GCC optimize("O2")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;

const int MAXN = 500100, MAXK = 30;
const ll MOD = 998244353;
const ll INF = 1e17;
const ld PI = asin(1) * 2;

vector<pair<ll, ll>> fairs[MAXN];
int n;
ll u, d;
int s;

ll dp[MAXN];
ll tree[2][4*MAXN];

void build (int tId, int id = 1, int le = 1, int ri = MAXN-1) {
    if (le == ri) {
        tree[tId][id] = -INF;
        return;
    }
    int mid = (le+ri)/2;
    build (tId, 2*id, le, mid);
    build (tId, 2*id+1, mid+1, ri);
    tree[tId][id] = max(tree[tId][2*id], tree[tId][2*id+1]);
}

void upd (int tId, int p, ll x, int id = 1, int le = 1, int ri = MAXN-1) {
    if (le == ri) {
        tree[tId][id] = max(x, tree[tId][id]);
        return;
    }
    int mid = (le+ri)/2;
    if (p <= mid)
        upd (tId, p, x, 2*id, le, mid);
    else
        upd (tId, p, x, 2*id+1, mid+1, ri);
    tree[tId][id] = max(tree[tId][2*id], tree[tId][2*id+1]);
}

ll getMax (int tId, int x, int y, int id = 1, int le = 1, int ri = MAXN-1) {
    if (x > ri || y < le) return -INF;
    if (x <= le && ri <= y) return tree[tId][id];
    int mid = (le+ri)/2;
    return max( getMax(tId, x, y, 2*id, le, mid), getMax(tId, x, y, 2*id+1, mid+1, ri) );
}

void ch (ll l) {
    upd (0, l, dp[l] + l*d);
    upd (1, l, dp[l] - l*u);
}

int main()
{
    FAST_IO;

    FOR(j, 0, 1) build (j);

    cin >> n >> u >> d >> s;

    fairs[MAXN-2].pb({s, 0});

    REP(n) {
        int t;
        ll l, m;
        cin >> t >> l >> m;
        fairs[t].pb({l, m});
    }

    FOR(i, 0, MAXN-1) FOR(j, 0, 1) upd (j, i, -INF);
    FOR(i, 0, MAXN-1) dp[i] = -INF;
    dp[s] = 0;
    ch(s);

    FOR(i, 0, MAXN-1) {
        if ((int)fairs[i].size() == 0) continue;
        sort(fairs[i].begin(), fairs[i].end());

        for (auto p : fairs[i]) {
            ll l = p.f, m = p.s;

            ll cur1 = m - l * d;
            cur1 += getMax(0, 1, l);

            ll cur2 = m + l * u;
            cur2 += getMax(1, l, MAXN-1);

            dp[l] = max(dp[l], cur1);
            dp[l] = max(dp[l], cur2);

        }

        for (auto p : fairs[i]) {
            ll l = p.f;

            ch (l);

          //  cout << " l = " << l << " dp = " << dp[l] << endl;
        }

        for (auto p : fairs[i]) {
            ll l = p.f, m = p.s;

            ll cur = m - l * d;
            cur += getMax(0, 1, l-1);

            upd (0, l, cur + l*d);

            dp[l] = max(dp[l], cur);

          //  cout << " l = " << l << " 0 " << " cur = " << cur << endl;

        }

        reverse(fairs[i].begin(), fairs[i].end());

        for (auto p : fairs[i]) {
            ll l = p.f, m = p.s;

            ll cur = m + l * u;
            cur += getMax(1, l+1, MAXN-1);

            upd (1, l, cur - l*u);

            dp[l] = max(dp[l], cur);

           // cout << " l = " << l << " 1 " << " cur = " << cur << endl;

        }

        //reverse(fairs[i].begin(), fairs[i].end());

        for (auto p : fairs[i]) {
            ll l = p.f;

            ch (l);

          //  cout << " l = " << l << " dp = " << dp[l] << endl;
        }
    }

    cout << dp[s] << "\n";

    return 0;
}


/*
2 1 10 5
1 4 100
1 6 50
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 32324 KB Output is correct
2 Correct 227 ms 32304 KB Output is correct
3 Correct 256 ms 32324 KB Output is correct
4 Correct 234 ms 32404 KB Output is correct
5 Correct 240 ms 32452 KB Output is correct
6 Correct 297 ms 32952 KB Output is correct
7 Correct 412 ms 33948 KB Output is correct
8 Correct 602 ms 35500 KB Output is correct
9 Correct 772 ms 37076 KB Output is correct
10 Correct 1204 ms 41872 KB Output is correct
11 Correct 1359 ms 41720 KB Output is correct
12 Correct 1701 ms 44900 KB Output is correct
13 Correct 1724 ms 44868 KB Output is correct
14 Correct 2017 ms 48160 KB Output is correct
15 Correct 1872 ms 48084 KB Output is correct
16 Correct 2102 ms 48072 KB Output is correct
17 Correct 241 ms 32304 KB Output is correct
18 Correct 229 ms 32324 KB Output is correct
19 Correct 238 ms 32452 KB Output is correct
20 Correct 233 ms 32380 KB Output is correct
21 Correct 235 ms 32368 KB Output is correct
22 Correct 245 ms 32496 KB Output is correct
23 Correct 242 ms 32452 KB Output is correct
24 Correct 246 ms 32556 KB Output is correct
25 Correct 577 ms 34496 KB Output is correct
26 Correct 900 ms 36472 KB Output is correct
27 Correct 1363 ms 39212 KB Output is correct
28 Correct 1443 ms 39776 KB Output is correct
29 Correct 2011 ms 41592 KB Output is correct
30 Correct 1890 ms 42380 KB Output is correct