Submission #335466

#	Time	Username	Problem	Language	Result	Execution time	Memory
335466		HynDuf	Salesman (IOI09_salesman)	C++11	100 / 100	264 ms	14060 KiB

salesman

#include <bits/stdc++.h>

#define task "S"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 5e5 + 2, INF = 2e9 + 1;
int n, D, U, S, dp[N], bitLD[N], bitRU[N], ndp[N];
struct Event
{
    int days, pos, money;
    bool operator < (const Event &oth)
    {
        return days < oth.days || (days == oth.days && pos < oth.pos);
    }
};
vector<Event> eve;
void updLD(int p, int v)
{
    for (; p < N; p += p & -p) bitLD[p] = max(bitLD[p], v);
}
int queryLD(int p)
{
    int res = -INF;
    for (; p; p -= p & -p) res = max(res, bitLD[p]);
    return res;
}
void updRU(int p, int v)
{
    for (; p; p -= p & -p) bitRU[p] = max(bitRU[p], v);
}
int queryRU(int p)
{
    int res = -INF;
    for (; p < N; p += p & -p) res = max(res, bitRU[p]);
    return res;
}
int main()
{
#ifdef HynDuf
    freopen(task".in", "r", stdin);
    //freopen(task".out", "w", stdout);
#else
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    cin >> n >> U >> D >> S;
    eve.assign(n + 1, {});
    rep(i, 1, n) cin >> eve[i].days >> eve[i].pos >> eve[i].money;
    fill(bitLD + 1, bitLD + N, -INF);
    fill(bitRU + 1, bitRU + N, -INF);
    sort(1 + all(eve));
    updLD(S, D * S);
    updRU(S, -U * S);
    for (int i = 1, j = 1; i <= n; i = j)
    {
        while (j <= n && eve[j].days == eve[i].days) j++;
        int curmx = -INF;
        rep(k, i, j - 1)
        {
            const Event &E = eve[k];
            ndp[k] = max(queryLD(E.pos) - D * E.pos, queryRU(E.pos) + U * E.pos) + E.money;
            dp[k] = max(ndp[k], curmx + E.money - D * E.pos);
            curmx = max(curmx + E.money, ndp[k] + D * E.pos);
        }
        curmx = -INF;
        Rep(k, j - 1, i)
        {
            const Event &E = eve[k];
            dp[k] = max(dp[k], curmx + E.money + U * E.pos);
            curmx = max(curmx + E.money, ndp[k] - U * E.pos);
            updLD(E.pos, dp[k] + D * E.pos);
            updRU(E.pos, dp[k] - U * E.pos);
        }
    }
    int ans = 0;
    rep(i, 1, n) ans = max(ans, dp[i] - ((eve[i].pos < S) ? D * (S - eve[i].pos) : U * (eve[i].pos - S)));
    cout << ans;
    return 0;
}

• Subtask 1: 100 / 100