oj.uz

Submission #861941

# Submission time Handle Problem Language Result Execution time Memory
861941 2023-10-17T08:26:17 Z 12345678 Salesman (IOI09_salesman) C++17
62 / 100
 400 ms 25628 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;
int n, u, d, s;
vector<tuple<int, int, int>> v;

struct segtree
{
    int d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=-2e9);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=max(d[i], vl));
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (r<ql||qr<l) return INT_MIN;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} up, dn;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>u>>d>>s;
    v.resize(n);
    for (auto &[x, y, z]:v) cin>>x>>y>>z;
    sort(v.begin(), v.end());
    up.build(1, nx-1, 1); dn.build(1, nx-1, 1);
    up.update(1, nx-1, 1, s, -s*u); dn.update(1, nx-1, 1, s, s*d);
    for (auto [x, y, z]:v)
    {
        int qup=up.query(1, nx-1, 1, y, nx-1);
        int qdn=dn.query(1, nx-1, 1, 1, y);
        int mx=max(qup+y*u, qdn-y*d)+z;
        //printf("%d %d %d %d %d %d\n", x, y, z, qup, qdn, mx);
        up.update(1, nx-1, 1, y, mx-y*u);
        dn.update(1, nx-1, 1, y, mx+y*d);
    }
    //cout<<up.query(1, nx-1, 1, s, nx-1)+s*u<<' '<<dn.query(1, nx-1, 1, 1, s)-s*d<<'\n';
    cout<<max(up.query(1, nx-1, 1, s, nx-1)+s*u, dn.query(1, nx-1, 1, 1, s)-s*d);
}

Subtask #1
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 5 ms 10844 KB Output is correct
5 Correct 6 ms 10844 KB Output is correct
6 Correct 22 ms 11452 KB Output is correct
7 Correct 48 ms 12116 KB Output is correct
8 Correct 75 ms 13656 KB Output is correct
9 Correct 118 ms 14828 KB Output is correct
10 Correct 222 ms 19060 KB Output is correct
11 Correct 222 ms 19540 KB Output is correct
12 Correct 295 ms 21900 KB Output is correct
13 Correct 291 ms 21780 KB Output is correct
14 Correct 373 ms 25628 KB Output is correct
15 Correct 323 ms 24616 KB Output is correct
16 Correct 400 ms 24744 KB Output is correct
17 Correct 3 ms 10844 KB Output is correct
18 Incorrect 4 ms 10844 KB Output isn't correct
19 Incorrect 4 ms 10844 KB Output isn't correct
20 Incorrect 5 ms 10908 KB Output isn't correct
21 Incorrect 5 ms 10840 KB Output isn't correct
22 Incorrect 7 ms 10844 KB Output isn't correct
23 Incorrect 6 ms 11008 KB Output isn't correct
24 Incorrect 7 ms 10944 KB Output isn't correct
25 Incorrect 71 ms 13392 KB Output isn't correct
26 Incorrect 140 ms 15824 KB Output isn't correct
27 Incorrect 238 ms 19284 KB Output isn't correct
28 Incorrect 251 ms 20308 KB Output isn't correct
29 Incorrect 330 ms 23120 KB Output isn't correct
30 Incorrect 337 ms 24112 KB Output isn't correct