oj.uz

Submission #928548

# Submission time Handle Problem Language Result Execution time Memory
928548 2024-02-16T16:05:42 Z boris_mihov Salesman (IOI09_salesman) C++17
60 / 100
 355 ms 27824 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 int INF = 2e9;

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

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

struct SegmentTree
{
    int 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, int 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]);
    }

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

        int 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);
    }

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

SegmentTree treeU;
SegmentTree treeD;
Event event[MAXN];
int 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 5 ms 14684 KB Output is correct
2 Correct 5 ms 14808 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 6 ms 14680 KB Output is correct
5 Correct 8 ms 14684 KB Output is correct
6 Correct 18 ms 15196 KB Output is correct
7 Correct 39 ms 17740 KB Output is correct
8 Correct 73 ms 18768 KB Output is correct
9 Correct 120 ms 19240 KB Output is correct
10 Correct 193 ms 23632 KB Output is correct
11 Correct 216 ms 24272 KB Output is correct
12 Correct 283 ms 25012 KB Output is correct
13 Correct 291 ms 25428 KB Output is correct
14 Correct 355 ms 27824 KB Output is correct
15 Correct 323 ms 27056 KB Output is correct
16 Correct 346 ms 26960 KB Output is correct
17 Incorrect 5 ms 14680 KB Output isn't correct
18 Incorrect 5 ms 14684 KB Output isn't correct
19 Incorrect 5 ms 14684 KB Output isn't correct
20 Incorrect 6 ms 14868 KB Output isn't correct
21 Incorrect 6 ms 14684 KB Output isn't correct
22 Incorrect 8 ms 14684 KB Output isn't correct
23 Incorrect 7 ms 14684 KB Output isn't correct
24 Incorrect 7 ms 14684 KB Output isn't correct
25 Incorrect 72 ms 18268 KB Output isn't correct
26 Incorrect 147 ms 21704 KB Output isn't correct
27 Incorrect 239 ms 23536 KB Output isn't correct
28 Incorrect 253 ms 24252 KB Output isn't correct
29 Incorrect 326 ms 25428 KB Output isn't correct
30 Incorrect 337 ms 26448 KB Output isn't correct