oj.uz

Submission #986685

# Submission time Handle Problem Language Result Execution time Memory
986685 2024-05-21T03:39:39 Z JooDdae Salesman (IOI09_salesman) C++17
100 / 100
 1085 ms 45560 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l+r) >> 1)

const int INF = 2e9, N = 5e5+1;

int n, u, d, s, mx[500500], t1[2002002], t2[2002002];
vector<array<int, 2>> v[500500];

void update(int t[], int id, int x, int node = 1, int l = 1, int r = N) {
    if(id < l || r < id) return;
    if(l == r) {
        t[node] = max(t[node], x);
        return;
    }
    if(id <= mid) update(t, id, x, node*2, l, mid);
    else update(t, id, x, node*2+1, mid+1, r);
    t[node] = max(t[node*2], t[node*2+1]);
}

int find(int t[], int nl, int nr, int node = 1, int l = 1, int r = N) {
    if(nr < l || r < nl) return -INF;
    if(nl <= l && r <= nr) return t[node];
    return max(find(t, nl, nr, node*2, l, mid), find(t, nl, nr, node*2+1, mid+1, r));
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> u >> d >> s;
    for(int i=1;i<=n;i++) {
        int t, x, y; cin >> t >> x >> y;
        v[t].push_back({x, y});
    }

    fill(t1, t1+4*N+1, -INF), fill(t2, t2+4*N+1, -INF);
    fill(mx, mx+N+1, -INF);
    update(t1, s, s*u), update(t2, s, -s*d);
    for(int t=1;t<=N;t++) if(!v[t].empty()) {
        sort(v[t].begin(), v[t].end());

        for(auto [x, y] : v[t]) mx[x] = max(find(t1, 1, x-1) - x*u, x*d + find(t2, x+1, N)) + y;

        for(auto [x, y] : v[t]) {
            update(t1, x, x*u+mx[x]);
            update(t2, x, mx[x]-x*d);
        }

        for(auto [x, y] : v[t]) {
            auto k = find(t1, 1, x-1) - x*u + y;
            mx[x] = max(mx[x], k), update(t1, x, x*u+k);
        }
        reverse(v[t].begin(), v[t].end());
        for(auto [x, y] : v[t]) {
            auto k = x*d + find(t2, x+1, N) + y;
            mx[x] = max(mx[x], k), update(t2, x, k-x*d);
        }

        for(auto [x, y] : v[t]) {
            update(t1, x, x*u+mx[x]);
            update(t2, x, mx[x]-x*d);
        }
    }

    int ans = 0;
    for(int i=1;i<=N;i++) {
        ans = max(ans, find(t1, 1, s-1) - s*u);
        ans = max(ans, s*d + find(t2, s+1, N));
    }
    cout << ans << "\n";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 29788 KB Output is correct
2 Correct 65 ms 29784 KB Output is correct
3 Correct 65 ms 29752 KB Output is correct
4 Correct 61 ms 29896 KB Output is correct
5 Correct 91 ms 29788 KB Output is correct
6 Correct 104 ms 30296 KB Output is correct
7 Correct 168 ms 31324 KB Output is correct
8 Correct 263 ms 32956 KB Output is correct
9 Correct 311 ms 34516 KB Output is correct
10 Correct 530 ms 39212 KB Output is correct
11 Correct 637 ms 38992 KB Output is correct
12 Correct 786 ms 42580 KB Output is correct
13 Correct 777 ms 42348 KB Output is correct
14 Correct 1002 ms 45476 KB Output is correct
15 Correct 933 ms 45468 KB Output is correct
16 Correct 1085 ms 45560 KB Output is correct
17 Correct 62 ms 29784 KB Output is correct
18 Correct 58 ms 29832 KB Output is correct
19 Correct 67 ms 30032 KB Output is correct
20 Correct 71 ms 29784 KB Output is correct
21 Correct 67 ms 29788 KB Output is correct
22 Correct 93 ms 29788 KB Output is correct
23 Correct 75 ms 29908 KB Output is correct
24 Correct 80 ms 29900 KB Output is correct
25 Correct 253 ms 30800 KB Output is correct
26 Correct 360 ms 31828 KB Output is correct
27 Correct 558 ms 33152 KB Output is correct
28 Correct 605 ms 33760 KB Output is correct
29 Correct 762 ms 34628 KB Output is correct
30 Correct 798 ms 34764 KB Output is correct