oj.uz

Submission #986689

# Submission time Handle Problem Language Result Execution time Memory
986689 2024-05-21T03:49:49 Z JooDdae Salesman (IOI09_salesman) C++17
100 / 100
 357 ms 42696 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[500500], t2[500500];
vector<array<int, 2>> v[500500];
 
void update(int t[], int b, int x) {
    while(b <= N) t[b] = max(t[b], x), b += b & -b;
}
 
int find(int t[], int b) {
    int re = -INF;
    while(b) re = max(re, t[b]), b -= b & -b;
    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+N+1, -INF), fill(t2, t2+N+1, -INF);
    fill(mx, mx+N+1, -INF);
    update(t1, s, s*u), update(t2, N-s+1, -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, x-1) - x*u, x*d + find(t2, N-x)) + y;
 
        for(auto [x, y] : v[t]) {
            update(t1, x, x*u+mx[x]);
            update(t2, N-x+1, mx[x]-x*d);
        }
 
        for(auto [x, y] : v[t]) {
            auto k = find(t1, 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, N-x) + y;
            mx[x] = max(mx[x], k), update(t2, N-x+1, k-x*d);
        }
 
        for(auto [x, y] : v[t]) {
            update(t1, x, x*u+mx[x]);
            update(t2, N-x+1, mx[x]-x*d);
        }
    }
 
    int ans = 0;
    for(int i=1;i<=N;i++) ans = max(ans, mx[i] - abs(i-s)*(i<s ? u:d));
    cout << ans << "\n";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18012 KB Output is correct
2 Correct 10 ms 18012 KB Output is correct
3 Correct 11 ms 18012 KB Output is correct
4 Correct 12 ms 18012 KB Output is correct
5 Correct 12 ms 18268 KB Output is correct
6 Correct 22 ms 19036 KB Output is correct
7 Correct 52 ms 20316 KB Output is correct
8 Correct 74 ms 22864 KB Output is correct
9 Correct 98 ms 24916 KB Output is correct
10 Correct 162 ms 32172 KB Output is correct
11 Correct 218 ms 32852 KB Output is correct
12 Correct 261 ms 36688 KB Output is correct
13 Correct 268 ms 36948 KB Output is correct
14 Correct 357 ms 42696 KB Output is correct
15 Correct 324 ms 41536 KB Output is correct
16 Correct 330 ms 41656 KB Output is correct
17 Correct 10 ms 18012 KB Output is correct
18 Correct 10 ms 17920 KB Output is correct
19 Correct 10 ms 18012 KB Output is correct
20 Correct 11 ms 17912 KB Output is correct
21 Correct 12 ms 18136 KB Output is correct
22 Correct 13 ms 18012 KB Output is correct
23 Correct 12 ms 18012 KB Output is correct
24 Correct 13 ms 18012 KB Output is correct
25 Correct 53 ms 20312 KB Output is correct
26 Correct 101 ms 22984 KB Output is correct
27 Correct 167 ms 25816 KB Output is correct
28 Correct 180 ms 27564 KB Output is correct
29 Correct 231 ms 29268 KB Output is correct
30 Correct 233 ms 30304 KB Output is correct