oj.uz

Submission #861810

# Submission time Handle Problem Language Result Execution time Memory
861810 2023-10-17T03:21:50 Z sleepntsheep Salesman (IOI09_salesman) C++17
5 / 100
 416 ms 44792 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll =long long;
using ld=long double;

const ll X = 500005, N = 555555;
int n, d, u, s;

struct binarytree
{
    ll t[X*2];
    binarytree() {memset(t,0xbf,sizeof t);}
    ll qry(int l, int r)
    {
        ll z = -1e18;
        for (l+=X,r+=X+1;l<r;l/=2,r/=2){
            if(l&1)z=max(z,t[l++]);
            if(r&1)z=max(t[--r],z);
        }
        return z;
    }
    void upd(int p, int k) { for(t[p+=X]=k;p/=2;)t[p]=max(t[p*2],t[p*2+1]); }
} thi, tlo;

struct fair
{
    int pos, money;
    bool operator<(const fair &o) const { return pos<o.pos; }
};
vector<fair> a[N];

void upd(ll pos, ll val)
{
    thi.upd(pos, val - u * pos);
    tlo.upd(pos, val - (X - pos) * d);
}

ll cost(int pos)
{
    return max(thi.qry(pos, X-1) + u * pos, tlo.qry(0, pos) + (X - pos) * d);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> u >> d >> s;
    for (int d, p, m, i = 0; i < n; ++i)
        cin >> d >> p >> m, a[d].push_back(fair{p, m});
    sort(a, a+n);
    upd(s, 0);
    for (auto i = 0; i <= 500000; ++i)
    {
        auto &x = a[i];
        if (x.empty()) continue;
        sort(x.begin(), x.end());
        if (x.size() == 1)
            upd(x[0].pos, x[0].money + cost(x[0].pos));
        else
        {
            vector<int> temp(x.size()), rtemp(x.size());
            for (int i = 0; i < x.size(); ++i) temp[i] = rtemp[i] = x[i].money + cost(x[i].pos);
            for (int i = 1; i < x.size(); ++i) temp[i] = max(temp[i], temp[i-1] + (x[i].pos - x[i-1].pos) * d + x[i].money);
            for (int i = (int)x.size(); i--;) rtemp[i] = max(rtemp[i], temp[i-1] + (x[i+1].pos - x[i].pos) * u + x[i].money);
            for (int i = 0; i < x.size(); ++i) upd(x[i].pos, max(temp[i], rtemp[i]));
        }
    }
    cout << cost(s);

    return 0;
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:71:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for (int i = 0; i < x.size(); ++i) temp[i] = rtemp[i] = x[i].money + cost(x[i].pos);
      |                             ~~^~~~~~~~~~
salesman.cpp:72:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for (int i = 1; i < x.size(); ++i) temp[i] = max(temp[i], temp[i-1] + (x[i].pos - x[i-1].pos) * d + x[i].money);
      |                             ~~^~~~~~~~~~
salesman.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for (int i = 0; i < x.size(); ++i) upd(x[i].pos, max(temp[i], rtemp[i]));
      |                             ~~^~~~~~~~~~

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Incorrect 6 ms 29020 KB Output isn't correct
4 Incorrect 6 ms 29020 KB Output isn't correct
5 Incorrect 9 ms 29272 KB Output isn't correct
6 Incorrect 21 ms 29532 KB Output isn't correct
7 Incorrect 51 ms 30704 KB Output isn't correct
8 Incorrect 94 ms 32080 KB Output isn't correct
9 Incorrect 114 ms 33732 KB Output isn't correct
10 Correct 223 ms 38736 KB Output is correct
11 Incorrect 255 ms 38480 KB Output isn't correct
12 Correct 281 ms 41660 KB Output is correct
13 Incorrect 315 ms 41560 KB Output isn't correct
14 Incorrect 347 ms 44632 KB Output isn't correct
15 Incorrect 416 ms 44792 KB Output isn't correct
16 Incorrect 384 ms 44624 KB Output isn't correct
17 Incorrect 5 ms 29020 KB Output isn't correct
18 Incorrect 5 ms 29020 KB Output isn't correct
19 Incorrect 6 ms 29020 KB Output isn't correct
20 Incorrect 6 ms 29100 KB Output isn't correct
21 Incorrect 7 ms 29020 KB Output isn't correct
22 Incorrect 8 ms 29240 KB Output isn't correct
23 Incorrect 8 ms 29020 KB Output isn't correct
24 Incorrect 9 ms 29272 KB Output isn't correct
25 Incorrect 60 ms 30040 KB Output isn't correct
26 Incorrect 112 ms 31284 KB Output isn't correct
27 Incorrect 192 ms 33112 KB Output isn't correct
28 Incorrect 200 ms 33100 KB Output isn't correct
29 Incorrect 292 ms 34196 KB Output isn't correct
30 Incorrect 274 ms 34764 KB Output isn't correct