oj.uz

Submission #1000869

# Submission time Handle Problem Language Result Execution time Memory
1000869 2024-06-18T10:37:14 Z fryingduc Salesman (IOI09_salesman) C++17
60 / 100
 572 ms 41520 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;
    }
} 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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31576 KB Output is correct
2 Correct 8 ms 31576 KB Output is correct
3 Correct 8 ms 31580 KB Output is correct
4 Correct 12 ms 31608 KB Output is correct
5 Correct 11 ms 31832 KB Output is correct
6 Correct 28 ms 34140 KB Output is correct
7 Correct 70 ms 34388 KB Output is correct
8 Correct 97 ms 34680 KB Output is correct
9 Correct 150 ms 34932 KB Output is correct
10 Correct 236 ms 38228 KB Output is correct
11 Correct 264 ms 38224 KB Output is correct
12 Correct 350 ms 40528 KB Output is correct
13 Correct 418 ms 40532 KB Output is correct
14 Correct 480 ms 41296 KB Output is correct
15 Correct 436 ms 41300 KB Output is correct
16 Correct 572 ms 41520 KB Output is correct
17 Incorrect 9 ms 31576 KB Output isn't correct
18 Incorrect 8 ms 31580 KB Output isn't correct
19 Incorrect 10 ms 31580 KB Output isn't correct
20 Incorrect 18 ms 31836 KB Output isn't correct
21 Incorrect 12 ms 31772 KB Output isn't correct
22 Incorrect 14 ms 31836 KB Output isn't correct
23 Incorrect 16 ms 31836 KB Output isn't correct
24 Incorrect 14 ms 31836 KB Output isn't correct
25 Incorrect 118 ms 33620 KB Output isn't correct
26 Incorrect 193 ms 35668 KB Output isn't correct
27 Incorrect 324 ms 38696 KB Output isn't correct
28 Incorrect 333 ms 38736 KB Output isn't correct
29 Incorrect 524 ms 41340 KB Output isn't correct
30 Incorrect 499 ms 41304 KB Output isn't correct