oj.uz

Submission #1000865

# Submission time Handle Problem Language Result Execution time Memory
1000865 2024-06-18T10:35:02 Z fryingduc Salesman (IOI09_salesman) C++17
60 / 100
 475 ms 50256 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 5e5 + 5;
const long long inf = 1e17;
int n, d, u, s;
long long f[maxn];

struct info {
    int t, l, m;
    bool operator<(const info &o) {
        return t < o.t;
    }
} a[maxn];

struct segment_tree {
    int n;
    vector<long long> tree;
    segment_tree() {}
    segment_tree(int n) : n(n), tree(n * 4 + 6, -inf) {}
    void update(int ind, int l, int r, int pos, long long val) {
        if(l == r) {
            tree[ind] = max(tree[ind], val);
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid) update(ind * 2, l, mid, pos, val);
        else update(ind * 2 + 1, mid + 1, r, pos, val);
        tree[ind] = max(tree[ind * 2], tree[ind * 2 + 1]);
    }
    long long get(int ind, int l, int r, int x, int y) {
        if(l > y || r < x) return -inf;
        if(x <= l and r <= y) return tree[ind];
        int mid = (l + r) / 2;
        return max(get(ind * 2, l, mid, x, y), get(ind * 2 + 1, mid + 1, r, x, y));
    }
    void update(int pos, long long val) {
        update(1, 1, n, pos, val);
    }
    long long get(int x, int y) {
        return get(1, 1, n, x, y);
    }
} up, down;
void solve() {
    cin >> n >> u >> d >> s;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i].t >> a[i].l >> a[i].m;
    }
    up = segment_tree(maxn);
    down = segment_tree(maxn);
    
    sort(a + 1, a + n + 1);
    down.update(s, -(s * u));
    up.update(s, s * d);  
    
    long long ans = 0;
    
    for(int i = 1; i <= n; ++i) {
        int cur_up = up.get(1, a[i].l - 1) - a[i].l * d + a[i].m; 
        int cur_down = down.get(a[i].l + 1, maxn - 1) + a[i].l * u + a[i].m;
        
        f[i] = max(cur_up, cur_down);
        up.update(a[i].l, f[i] + a[i].l * d);
        down.update(a[i].l, f[i] - a[i].l * u);
        
        if(a[i].l >= s) {
            ans = max(ans, f[i] - 1ll * (a[i].l - s) * u);
        }
        else {
            ans = max(ans, f[i] - (s - a[i].l) * d);
        }
//        cerr << i << " " << f[i] << " " << cur_up << " " << cur_down << '\n';
    }
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31580 KB Output is correct
2 Correct 5 ms 31580 KB Output is correct
3 Correct 6 ms 31820 KB Output is correct
4 Correct 7 ms 31756 KB Output is correct
5 Correct 9 ms 31836 KB Output is correct
6 Correct 24 ms 34396 KB Output is correct
7 Correct 55 ms 35080 KB Output is correct
8 Correct 94 ms 36432 KB Output is correct
9 Correct 144 ms 37336 KB Output is correct
10 Correct 232 ms 42980 KB Output is correct
11 Correct 268 ms 43744 KB Output is correct
12 Correct 356 ms 46776 KB Output is correct
13 Correct 352 ms 46928 KB Output is correct
14 Correct 475 ms 50256 KB Output is correct
15 Correct 381 ms 49488 KB Output is correct
16 Correct 432 ms 49384 KB Output is correct
17 Incorrect 8 ms 31580 KB Output isn't correct
18 Incorrect 6 ms 31720 KB Output isn't correct
19 Incorrect 7 ms 31580 KB Output isn't correct
20 Incorrect 7 ms 31836 KB Output isn't correct
21 Incorrect 7 ms 31836 KB Output isn't correct
22 Incorrect 9 ms 31836 KB Output isn't correct
23 Incorrect 9 ms 31832 KB Output isn't correct
24 Incorrect 10 ms 31836 KB Output isn't correct
25 Incorrect 88 ms 36116 KB Output isn't correct
26 Incorrect 162 ms 40272 KB Output isn't correct
27 Incorrect 305 ms 43088 KB Output isn't correct
28 Incorrect 280 ms 44116 KB Output isn't correct
29 Incorrect 407 ms 48212 KB Output isn't correct
30 Incorrect 456 ms 48724 KB Output isn't correct