oj.uz

답안 #861823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861823 2023-10-17T03:30:48 Z sleepntsheep Salesman (IOI09_salesman) C++17
100 / 100
 376 ms 37420 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 int N = 500005;
const ll inf = 1e9;
int n, d, u, s;

struct binarytree
{
    int t[N*2];
    binarytree() {memset(t,0xbf,sizeof t);}
    inline int qry(int l, int r)
    {
        int z=-1e9;
        for (l+=N,r+=N+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;
    }
    inline void upd(int p, int k) { for(t[p+=N]=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];

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

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

int temp[N], rtemp[N];

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
        {
            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: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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 21596 KB Output is correct
2 Correct 4 ms 21596 KB Output is correct
3 Correct 4 ms 21596 KB Output is correct
4 Correct 5 ms 21684 KB Output is correct
5 Correct 6 ms 21852 KB Output is correct
6 Correct 18 ms 22344 KB Output is correct
7 Correct 36 ms 23128 KB Output is correct
8 Correct 78 ms 24820 KB Output is correct
9 Correct 117 ms 26196 KB Output is correct
10 Correct 179 ms 31060 KB Output is correct
11 Correct 205 ms 31080 KB Output is correct
12 Correct 259 ms 34136 KB Output is correct
13 Correct 291 ms 34216 KB Output is correct
14 Correct 376 ms 37416 KB Output is correct
15 Correct 327 ms 37172 KB Output is correct
16 Correct 355 ms 37420 KB Output is correct
17 Correct 5 ms 23644 KB Output is correct
18 Correct 5 ms 23644 KB Output is correct
19 Correct 5 ms 23644 KB Output is correct
20 Correct 6 ms 23644 KB Output is correct
21 Correct 6 ms 23800 KB Output is correct
22 Correct 8 ms 23640 KB Output is correct
23 Correct 7 ms 23644 KB Output is correct
24 Correct 6 ms 23644 KB Output is correct
25 Correct 56 ms 24764 KB Output is correct
26 Correct 106 ms 25940 KB Output is correct
27 Correct 178 ms 27184 KB Output is correct
28 Correct 190 ms 27820 KB Output is correct
29 Correct 241 ms 28500 KB Output is correct
30 Correct 248 ms 28872 KB Output is correct