oj.uz

Submission #861818

# Submission time Handle Problem Language Result Execution time Memory
861818 2023-10-17T03:27:10 Z sleepntsheep Salesman (IOI09_salesman) C++17
60 / 100
 402 ms 49492 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, inf = 1e18;
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});
    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<ll> temp(x.size(), -inf), rtemp(x.size(), -inf);
            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() - 2; i >= 0; --i) rtemp[i] = max(rtemp[i], rtemp[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:69:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int i = 0; i < x.size(); ++i) temp[i] = rtemp[i] = x[i].money + cost(x[i].pos);
      |                             ~~^~~~~~~~~~
salesman.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             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: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 = 0; i < x.size(); ++i) upd(x[i].pos, max(temp[i], rtemp[i]));
      |                             ~~^~~~~~~~~~

Subtask #1
60.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 Correct 6 ms 29020 KB Output is correct
4 Correct 7 ms 29020 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 22 ms 30140 KB Output is correct
7 Correct 56 ms 31120 KB Output is correct
8 Correct 94 ms 33360 KB Output is correct
9 Correct 129 ms 35624 KB Output is correct
10 Correct 214 ms 41296 KB Output is correct
11 Correct 246 ms 41552 KB Output is correct
12 Correct 338 ms 44880 KB Output is correct
13 Correct 329 ms 45244 KB Output is correct
14 Correct 391 ms 49492 KB Output is correct
15 Correct 370 ms 49136 KB Output is correct
16 Correct 402 ms 49144 KB Output is correct
17 Incorrect 6 ms 29020 KB Output isn't correct
18 Incorrect 6 ms 29116 KB Output isn't correct
19 Incorrect 6 ms 29020 KB Output isn't correct
20 Incorrect 7 ms 29172 KB Output isn't correct
21 Incorrect 7 ms 29020 KB Output isn't correct
22 Incorrect 8 ms 29276 KB Output isn't correct
23 Incorrect 8 ms 29284 KB Output isn't correct
24 Incorrect 8 ms 29104 KB Output isn't correct
25 Incorrect 62 ms 31204 KB Output isn't correct
26 Incorrect 139 ms 33440 KB Output isn't correct
27 Incorrect 188 ms 36632 KB Output isn't correct
28 Incorrect 194 ms 36428 KB Output isn't correct
29 Incorrect 268 ms 38212 KB Output isn't correct
30 Incorrect 282 ms 39684 KB Output isn't correct