oj.uz

Submission #335466

# Submission time Handle Problem Language Result Execution time Memory
335466 2020-12-12T17:34:19 Z HynDuf Salesman (IOI09_salesman) C++11
100 / 100
 264 ms 14060 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4204 KB Output is correct
4 Correct 4 ms 4332 KB Output is correct
5 Correct 5 ms 4332 KB Output is correct
6 Correct 14 ms 4716 KB Output is correct
7 Correct 29 ms 5228 KB Output is correct
8 Correct 56 ms 6252 KB Output is correct
9 Correct 79 ms 7156 KB Output is correct
10 Correct 150 ms 10196 KB Output is correct
11 Correct 163 ms 10220 KB Output is correct
12 Correct 210 ms 12140 KB Output is correct
13 Correct 212 ms 12140 KB Output is correct
14 Correct 264 ms 14060 KB Output is correct
15 Correct 248 ms 14060 KB Output is correct
16 Correct 264 ms 14060 KB Output is correct
17 Correct 3 ms 4204 KB Output is correct
18 Correct 3 ms 4204 KB Output is correct
19 Correct 4 ms 4332 KB Output is correct
20 Correct 4 ms 4332 KB Output is correct
21 Correct 4 ms 4332 KB Output is correct
22 Correct 5 ms 4332 KB Output is correct
23 Correct 5 ms 4332 KB Output is correct
24 Correct 5 ms 4332 KB Output is correct
25 Correct 53 ms 6252 KB Output is correct
26 Correct 103 ms 8172 KB Output is correct
27 Correct 181 ms 11116 KB Output is correct
28 Correct 189 ms 11244 KB Output is correct
29 Correct 247 ms 14060 KB Output is correct
30 Correct 260 ms 14060 KB Output is correct