oj.uz

Submission #928552

# Submission time Handle Problem Language Result Execution time Memory
928552 2024-02-16T16:08:24 Z boris_mihov Salesman (IOI09_salesman) C++17
60 / 100
 409 ms 31448 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 500000 + 10;
const llong INF = 1e18;

int n;
llong d, u;
struct Event
{
    int pos;
    int time;
    llong cost;

    friend bool operator < (const Event &a, const Event &b)
    {
        return a.time < b.time;
    }
};

struct SegmentTree
{
    llong tree[4*MAXN];
    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node] = -INF;
            return;
        }   

        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);
        tree[node] = std::max(tree[2*node], tree[2*node + 1]);
    }

    void update(int l, int r, int node, int queryPos, llong queryVal)
    {
        if (l == r)
        {
            tree[node] = std::max(tree[node], queryVal);
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
        else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
        tree[node] = std::max(tree[2*node], tree[2*node + 1]);
    }

    llong query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        llong res = -INF;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) res = std::max(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void build()
    {
        build(1, MAXN - 1, 1);
    }

    void update(int pos, int val)
    {
        update(1, MAXN - 1, 1, pos, val);
    }

    llong query(int l, int r)
    {
        return query(1, MAXN - 1, 1, l, r);
    }
};

SegmentTree treeU;
SegmentTree treeD;
Event event[MAXN];
llong dp[MAXN];

void solve()
{
    treeU.build();
    treeD.build();
    std::sort(event + 1, event + 1 + n);
    for (int i = n ; i >= 0 ; --i)
    {
        if (event[i].pos <= event[0].pos) dp[i] = -(event[0].pos - event[i].pos) * d;
        else dp[i] = -(event[i].pos - event[0].pos) * u;

        dp[i] = std::max(dp[i], treeU.query(1, event[i].pos) - event[i].pos * u);
        dp[i] = std::max(dp[i], treeD.query(event[i].pos, MAXN - 1) + event[i].pos * d);
        treeU.update(event[i].pos, dp[i] + event[i].cost + event[i].pos * u);
        treeD.update(event[i].pos, dp[i] + event[i].cost - event[i].pos * d);
    }

    std::cout << dp[0] << '\n';
}

void input()
{
    std::cin >> n >> u >> d >> event[0].pos;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> event[i].time >> event[i].pos >> event[i].cost;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22876 KB Output is correct
2 Correct 5 ms 22872 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 8 ms 23040 KB Output is correct
6 Correct 21 ms 23132 KB Output is correct
7 Correct 49 ms 27144 KB Output is correct
8 Correct 87 ms 27204 KB Output is correct
9 Correct 113 ms 27220 KB Output is correct
10 Correct 230 ms 31316 KB Output is correct
11 Correct 290 ms 31448 KB Output is correct
12 Correct 338 ms 31316 KB Output is correct
13 Correct 352 ms 31316 KB Output is correct
14 Correct 409 ms 31432 KB Output is correct
15 Correct 377 ms 31224 KB Output is correct
16 Correct 406 ms 31316 KB Output is correct
17 Incorrect 5 ms 22876 KB Output isn't correct
18 Incorrect 6 ms 22876 KB Output isn't correct
19 Incorrect 6 ms 22876 KB Output isn't correct
20 Incorrect 7 ms 22876 KB Output isn't correct
21 Incorrect 7 ms 23132 KB Output isn't correct
22 Incorrect 9 ms 22876 KB Output isn't correct
23 Incorrect 8 ms 23040 KB Output isn't correct
24 Incorrect 8 ms 22876 KB Output isn't correct
25 Incorrect 82 ms 27220 KB Output isn't correct
26 Incorrect 172 ms 29268 KB Output isn't correct
27 Incorrect 268 ms 31312 KB Output isn't correct
28 Incorrect 284 ms 31188 KB Output isn't correct
29 Incorrect 369 ms 31316 KB Output isn't correct
30 Incorrect 397 ms 31316 KB Output isn't correct