oj.uz

Submission #986687

# Submission time Handle Problem Language Result Execution time Memory
986687 2024-05-21T03:43:01 Z JooDdae Salesman (IOI09_salesman) C++17
100 / 100
 998 ms 45468 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];
  
    int re = -INF;
    if(nl <= mid) re = max(re, find(t, nl, nr, node*2, l, mid));
    if(mid < nr) re = max(re, find(t, nl, nr, node*2+1, mid+1, r));
    return re;
}
 
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 70 ms 29784 KB Output is correct
2 Correct 74 ms 30032 KB Output is correct
3 Correct 73 ms 29832 KB Output is correct
4 Correct 68 ms 29788 KB Output is correct
5 Correct 81 ms 29968 KB Output is correct
6 Correct 136 ms 30300 KB Output is correct
7 Correct 188 ms 31160 KB Output is correct
8 Correct 255 ms 32940 KB Output is correct
9 Correct 327 ms 34520 KB Output is correct
10 Correct 508 ms 39208 KB Output is correct
11 Correct 712 ms 39204 KB Output is correct
12 Correct 845 ms 42336 KB Output is correct
13 Correct 788 ms 42336 KB Output is correct
14 Correct 998 ms 45468 KB Output is correct
15 Correct 850 ms 45468 KB Output is correct
16 Correct 985 ms 45468 KB Output is correct
17 Correct 72 ms 29784 KB Output is correct
18 Correct 62 ms 29784 KB Output is correct
19 Correct 76 ms 29784 KB Output is correct
20 Correct 74 ms 29784 KB Output is correct
21 Correct 98 ms 29788 KB Output is correct
22 Correct 79 ms 30032 KB Output is correct
23 Correct 78 ms 29784 KB Output is correct
24 Correct 83 ms 29788 KB Output is correct
25 Correct 217 ms 30800 KB Output is correct
26 Correct 384 ms 32080 KB Output is correct
27 Correct 562 ms 33084 KB Output is correct
28 Correct 671 ms 33752 KB Output is correct
29 Correct 778 ms 34688 KB Output is correct
30 Correct 763 ms 34896 KB Output is correct