Submission #842030

#	Time	Username	Problem	Language	Result	Execution time	Memory
842030		leeunchong	Salesman (IOI09_salesman)	C++17	2 / 100	461 ms	43488 KiB

salesman

#include <bits/stdc++.h>
#define POS first
#define VAL second
using namespace std;
using ll = long long;
using vpi = vector<pair<ll, ll>>;

const int MAX = 500009;
const ll INF = 0x3f3f3f3f;
vpi arr[MAX];
ll n, u, d, s;
ll tree_u[2*MAX], tree_d[2*MAX];

ll getMax(ll *arr, ll l, ll r) {
    ll ret = -INF;
    for(l += MAX, r += MAX; l<=r; l>>=1, r>>=1) {
        if(l&1) ret = max(ret, arr[l++]);
        if(~r&1) ret = max(ret, arr[r--]);
    }
    return ret;
}

void update(ll *arr, ll idx, ll val) {
    idx += MAX;
    arr[idx] = max(arr[idx], val);
    for(;idx>1;idx>>=1) {
        arr[idx>>1] = max(arr[idx], arr[idx^1]);
    }
}

void updateUD(ll idx, ll val) {
    update(tree_u, idx, val - u * idx);
    update(tree_d, idx, val + d * idx);
}

ll getDP(ll idx) {
    return max(getMax(tree_d, 0, idx) - d * idx, getMax(tree_u, idx, MAX-1) + u*idx);
}

ll i;
void query_market(vpi &market) {
    ll j = 0;
    if(market.size() == 0) { return; }
    sort(market.begin(), market.end());
    vector<ll> up, down;
    ll sz = market.size();
    
    for(j=0; j<sz; j++) {
        ll tmp = getDP(market[j].POS);
        up.push_back(tmp);
        down.push_back(tmp);
    }
    for(j=0; j<sz; j++) {
        if(j != 0) { down[j] = max(down[j], down[j-1] - d * (market[j].POS - market[j-1].POS));}
        down[j] += market[j].VAL;
    }
    for(j=sz-1; j>=0; j--) {
        if(j != sz-1) { up[j] = max(up[j], up[j-1] - u * (market[j+1].POS - market[j].POS)); }
        up[j] += market[j].VAL;
    }
    
    for(j=0; j<sz; j++) {
        updateUD(market[j].POS, max(up[j], down[j]));
    }
}

void fastIO() {
    ios::sync_with_stdio(false); cin.tie(0);
}

void input() {
    scanf("%d %d %d %d",&n,&u,&d,&s);
    ll a, b, c;
    for(int x = 0; x<n; x++) {
        scanf("%d %d %d",&a,&b,&c);
        arr[a].push_back({b, c});
    }
}

void solve() {
    memset(tree_u, 0xc0, sizeof(tree_u));
    memset(tree_d, 0xc0, sizeof(tree_d));
    updateUD(s, 0);
    for(i=1; i<=500001; i++) {
        query_market(arr[i]);
    }
    printf("%d",getDP(s));
}

int main() {
    fastIO();
    input();
    solve(); 
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'void input()':
salesman.cpp:72:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   72 |     scanf("%d %d %d %d",&n,&u,&d,&s);
      |            ~^           ~~
      |             |           |
      |             int*        ll* {aka long long int*}
      |            %lld
salesman.cpp:72:16: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
   72 |     scanf("%d %d %d %d",&n,&u,&d,&s);
      |               ~^           ~~
      |                |           |
      |                int*        ll* {aka long long int*}
      |               %lld
salesman.cpp:72:19: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll*' {aka 'long long int*'} [-Wformat=]
   72 |     scanf("%d %d %d %d",&n,&u,&d,&s);
      |                  ~^           ~~
      |                   |           |
      |                   int*        ll* {aka long long int*}
      |                  %lld
salesman.cpp:72:22: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'll*' {aka 'long long int*'} [-Wformat=]
   72 |     scanf("%d %d %d %d",&n,&u,&d,&s);
      |                     ~^           ~~
      |                      |           |
      |                      int*        ll* {aka long long int*}
      |                     %lld
salesman.cpp:75:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   75 |         scanf("%d %d %d",&a,&b,&c);
      |                ~^        ~~
      |                 |        |
      |                 int*     ll* {aka long long int*}
      |                %lld
salesman.cpp:75:20: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
   75 |         scanf("%d %d %d",&a,&b,&c);
      |                   ~^        ~~
      |                    |        |
      |                    int*     ll* {aka long long int*}
      |                   %lld
salesman.cpp:75:23: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll*' {aka 'long long int*'} [-Wformat=]
   75 |         scanf("%d %d %d",&a,&b,&c);
      |                      ~^        ~~
      |                       |        |
      |                       int*     ll* {aka long long int*}
      |                      %lld
salesman.cpp: In function 'void solve()':
salesman.cpp:87:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
   87 |     printf("%d",getDP(s));
      |             ~^  ~~~~~~~~
      |              |       |
      |              int     ll {aka long long int}
      |             %lld
salesman.cpp: In function 'void input()':
salesman.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d %d %d %d",&n,&u,&d,&s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d %d %d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 100