oj.uz

Submission #861812

# Submission time Handle Problem Language Result Execution time Memory
861812 2023-10-17T03:24:12 Z sleepntsheep Salesman (IOI09_salesman) C++17
60 / 100
 416 ms 44884 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});
    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(), -1000000000), rtemp(x.size(), -1000000000);
            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: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 5 ms 29020 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 23 ms 29788 KB Output is correct
7 Correct 43 ms 30556 KB Output is correct
8 Correct 81 ms 32088 KB Output is correct
9 Correct 117 ms 33832 KB Output is correct
10 Correct 204 ms 38480 KB Output is correct
11 Correct 275 ms 38528 KB Output is correct
12 Correct 326 ms 41640 KB Output is correct
13 Correct 319 ms 41756 KB Output is correct
14 Correct 377 ms 44624 KB Output is correct
15 Correct 416 ms 44884 KB Output is correct
16 Correct 389 ms 44628 KB Output is correct
17 Incorrect 6 ms 29016 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 7 ms 29016 KB Output isn't correct
21 Incorrect 6 ms 29020 KB Output isn't correct
22 Incorrect 7 ms 29064 KB Output isn't correct
23 Incorrect 7 ms 29020 KB Output isn't correct
24 Incorrect 7 ms 29016 KB Output isn't correct
25 Incorrect 66 ms 29992 KB Output isn't correct
26 Incorrect 113 ms 31316 KB Output isn't correct
27 Incorrect 232 ms 32924 KB Output isn't correct
28 Incorrect 239 ms 33332 KB Output isn't correct
29 Incorrect 290 ms 33832 KB Output isn't correct
30 Incorrect 328 ms 34836 KB Output isn't correct