oj.uz

Submission #1000934

# Submission time Handle Problem Language Result Execution time Memory
1000934 2024-06-18T11:30:33 Z fryingduc Salesman (IOI09_salesman) C++17
65 / 100
 566 ms 44216 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;

int m[maxn];
 
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);
    
    for(int i = 1; i <= n; ++i) {
        m[i] = m[i - 1] + a[i].m;
    }
    
    down.update(s, -(s * u));
    up.update(s, s * d);  
    
    long long ans = 0;
    
    for(int i = 1; i <= n; ++i) {
        int cur = 0;
        while(i + cur <= n and a[i].t == a[i + cur].t) ++cur;
        for(int j = i; j < i + cur; ++j) {
            long long cur_up = up.get(1, a[j].l - 1) - 1ll * a[j].l * d + a[j].m; 
            long long cur_down = down.get(a[j].l + 1, maxn - 1) + 1ll * a[j].l * u + a[j].m;
            
            f[j] = max(cur_up, cur_down);
        }
        long long current = f[i];
        vector<long long> suf(cur + 1, -inf), pref(cur + 1, -inf);
        vector<long long> tmp(cur, -inf);
        for(int j = i + cur - 1; j >= i; --j) {
            suf[j - i] = m[j] - a[j].l * (u + d);
            if(j < i + cur - 1) suf[j - i] = max(suf[j - i], suf[j - i + 1]);
        }
        for(int j = i; j < i + cur; ++j) {
            pref[j - i] = a[j].l * (u + d) - m[j - 1];
            if(j > i) pref[j - i] = max(pref[j - i], pref[j - i - 1]);
        }
        for(int j = i; j < i + cur; ++j) {
            if(j > i) current = max(f[j], current - (a[j].l - a[j - 1].l) * d + a[j].m);
            tmp[j - i] = current + max(0ll, suf[j - i] - m[j] + a[j].l * (u + d));
        }
        current = f[i];
        for(int j = i + cur - 1; j >= i; --j) {
            if(j < i + cur - 1) current = max(f[j], current - 1ll * (a[j + 1].l - a[j].l) * u + a[j].m);
            long long hehe = current + max(0ll, pref[j - i] + m[j - 1] - a[j].l * (u + d));
            tmp[j - i] = max(tmp[j - i], hehe);
        }
        for(int j = i; j < i + cur; ++j) {
            f[j] = max(f[j], tmp[j - i]);
            if(a[j].l >= s) {
                ans = max(ans, f[j] - 1ll * (a[j].l - s) * u);
            }
            else {
                ans = max(ans, f[j] - 1ll * (s - a[j].l) * d);
            }
            up.update(a[j].l, f[j] + 1ll * a[j].l * d);
            down.update(a[j].l, f[j] - 1ll * a[j].l * u);
        }
        i = i + cur - 1;
//        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
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31656 KB Output is correct
2 Correct 9 ms 31580 KB Output is correct
3 Correct 9 ms 31580 KB Output is correct
4 Correct 10 ms 31600 KB Output is correct
5 Correct 13 ms 31836 KB Output is correct
6 Correct 32 ms 34116 KB Output is correct
7 Correct 83 ms 34388 KB Output is correct
8 Correct 149 ms 35152 KB Output is correct
9 Correct 167 ms 35728 KB Output is correct
10 Correct 352 ms 39508 KB Output is correct
11 Correct 368 ms 39532 KB Output is correct
12 Correct 509 ms 42196 KB Output is correct
13 Correct 523 ms 41044 KB Output is correct
14 Correct 540 ms 43432 KB Output is correct
15 Correct 489 ms 43460 KB Output is correct
16 Correct 566 ms 43344 KB Output is correct
17 Incorrect 11 ms 31580 KB Output isn't correct
18 Incorrect 11 ms 31716 KB Output isn't correct
19 Incorrect 11 ms 31836 KB Output isn't correct
20 Correct 13 ms 31832 KB Output is correct
21 Correct 13 ms 31836 KB Output is correct
22 Incorrect 15 ms 31832 KB Output isn't correct
23 Incorrect 21 ms 31844 KB Output isn't correct
24 Correct 18 ms 31836 KB Output is correct
25 Incorrect 115 ms 33988 KB Output isn't correct
26 Incorrect 202 ms 36660 KB Output isn't correct
27 Incorrect 307 ms 40896 KB Output isn't correct
28 Incorrect 349 ms 40252 KB Output isn't correct
29 Correct 467 ms 43616 KB Output is correct
30 Incorrect 421 ms 44216 KB Output isn't correct