oj.uz

Submission #928551

# Submission time Handle Problem Language Result Execution time Memory
928551 2024-02-16T16:06:49 Z boris_mihov Salesman (IOI09_salesman) C++17
0 / 100
 402 ms 31620 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 = 4e18;

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

    int 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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 23128 KB Output isn't correct
2 Incorrect 5 ms 22876 KB Output isn't correct
3 Incorrect 6 ms 22876 KB Output isn't correct
4 Incorrect 6 ms 22876 KB Output isn't correct
5 Incorrect 8 ms 22876 KB Output isn't correct
6 Incorrect 20 ms 23100 KB Output isn't correct
7 Incorrect 49 ms 27164 KB Output isn't correct
8 Incorrect 102 ms 27116 KB Output isn't correct
9 Incorrect 114 ms 27120 KB Output isn't correct
10 Incorrect 224 ms 31316 KB Output isn't correct
11 Incorrect 268 ms 31448 KB Output isn't correct
12 Incorrect 330 ms 31216 KB Output isn't correct
13 Incorrect 356 ms 31188 KB Output isn't correct
14 Incorrect 396 ms 31188 KB Output isn't correct
15 Incorrect 358 ms 31180 KB Output isn't correct
16 Incorrect 402 ms 31224 KB Output isn't correct
17 Incorrect 5 ms 22876 KB Output isn't correct
18 Incorrect 5 ms 22876 KB Output isn't correct
19 Incorrect 6 ms 22876 KB Output isn't correct
20 Incorrect 7 ms 22872 KB Output isn't correct
21 Incorrect 7 ms 23036 KB Output isn't correct
22 Incorrect 8 ms 22876 KB Output isn't correct
23 Incorrect 8 ms 22876 KB Output isn't correct
24 Incorrect 9 ms 22876 KB Output isn't correct
25 Incorrect 91 ms 27120 KB Output isn't correct
26 Incorrect 171 ms 29268 KB Output isn't correct
27 Incorrect 279 ms 31316 KB Output isn't correct
28 Incorrect 273 ms 31620 KB Output isn't correct
29 Incorrect 371 ms 31220 KB Output isn't correct
30 Incorrect 375 ms 31308 KB Output isn't correct