oj.uz

Submission #1000874

# Submission time Handle Problem Language Result Execution time Memory
1000874 2024-06-18T10:43:43 Z fryingduc Salesman (IOI09_salesman) C++17
62 / 100
 479 ms 41552 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 = 9e18;
 
struct info {
    int t, l, m;
    bool operator<(const info &o) {
        return (t != o.t ? t < o.t : l < o.l);
    }
} 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) - 1ll * a[i].l * d + a[i].m; 
        long long cur_down = down.get(a[i].l + 1, maxn - 1) + 1ll * 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] - 1ll * (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
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31576 KB Output is correct
2 Correct 7 ms 31576 KB Output is correct
3 Correct 7 ms 31580 KB Output is correct
4 Correct 7 ms 31808 KB Output is correct
5 Correct 9 ms 31836 KB Output is correct
6 Correct 25 ms 34136 KB Output is correct
7 Correct 50 ms 34332 KB Output is correct
8 Correct 119 ms 34644 KB Output is correct
9 Correct 141 ms 35172 KB Output is correct
10 Correct 231 ms 38256 KB Output is correct
11 Correct 274 ms 38228 KB Output is correct
12 Correct 351 ms 40604 KB Output is correct
13 Correct 360 ms 40532 KB Output is correct
14 Correct 441 ms 41300 KB Output is correct
15 Correct 363 ms 41552 KB Output is correct
16 Correct 479 ms 41552 KB Output is correct
17 Correct 7 ms 31580 KB Output is correct
18 Incorrect 7 ms 31580 KB Output isn't correct
19 Incorrect 7 ms 31580 KB Output isn't correct
20 Incorrect 9 ms 31836 KB Output isn't correct
21 Incorrect 9 ms 31836 KB Output isn't correct
22 Incorrect 12 ms 31860 KB Output isn't correct
23 Incorrect 10 ms 31832 KB Output isn't correct
24 Incorrect 10 ms 31744 KB Output isn't correct
25 Incorrect 91 ms 34768 KB Output isn't correct
26 Incorrect 168 ms 37580 KB Output isn't correct
27 Incorrect 271 ms 38736 KB Output isn't correct
28 Incorrect 286 ms 38736 KB Output isn't correct
29 Incorrect 401 ms 41296 KB Output isn't correct
30 Incorrect 373 ms 41300 KB Output isn't correct