oj.uz

Submission #1000867

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

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

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) {
        long long cur_up = up.get(1, a[i].l - 1) - a[i].l * d + a[i].m; 
        long long 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] + 1ll * a[i].l * d);
        down.update(a[i].l, f[i] - 1ll * 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 31576 KB Output is correct
2 Correct 6 ms 31580 KB Output is correct
3 Correct 6 ms 31736 KB Output is correct
4 Correct 7 ms 31836 KB Output is correct
5 Correct 9 ms 31832 KB Output is correct
6 Correct 24 ms 34088 KB Output is correct
7 Correct 52 ms 34140 KB Output is correct
8 Correct 95 ms 34640 KB Output is correct
9 Correct 138 ms 35032 KB Output is correct
10 Correct 236 ms 38252 KB Output is correct
11 Correct 267 ms 38224 KB Output is correct
12 Correct 350 ms 40756 KB Output is correct
13 Correct 340 ms 40568 KB Output is correct
14 Correct 444 ms 41296 KB Output is correct
15 Correct 357 ms 41296 KB Output is correct
16 Correct 434 ms 41556 KB Output is correct
17 Incorrect 7 ms 31636 KB Output isn't correct
18 Incorrect 7 ms 31560 KB Output isn't correct
19 Incorrect 6 ms 33628 KB Output isn't correct
20 Incorrect 7 ms 31608 KB Output isn't correct
21 Incorrect 8 ms 31624 KB Output isn't correct
22 Incorrect 9 ms 31836 KB Output isn't correct
23 Incorrect 9 ms 31836 KB Output isn't correct
24 Incorrect 9 ms 31696 KB Output isn't correct
25 Incorrect 86 ms 34724 KB Output isn't correct
26 Incorrect 173 ms 37460 KB Output isn't correct
27 Incorrect 280 ms 38768 KB Output isn't correct
28 Incorrect 300 ms 38736 KB Output isn't correct
29 Incorrect 444 ms 41340 KB Output isn't correct
30 Incorrect 407 ms 41296 KB Output isn't correct