Submission #842026

#	Time	Username	Problem	Language	Result	Execution time	Memory
842026		leeunchong	Salesman (IOI09_salesman)	C++17	60 / 100	464 ms	43492 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) {
        ll cl = l, cr = r;
        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);
    ll check = arr[idx];
    for(;idx>1;idx>>=1) {
        arr[idx>>1] = max(arr[idx], arr[idx^1]);
    }
    ll check2 = idx;
}

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() {
    cin>>n>>u>>d>>s;
    ll a, b, c;
    for(int x = 0; x<n; x++) {
        cin>>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]);
    }
    cout<<getDP(s);
}

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

Compilation message (stderr)

salesman.cpp: In function 'll getMax(ll*, ll, ll)':
salesman.cpp:17:12: warning: unused variable 'cl' [-Wunused-variable]
   17 |         ll cl = l, cr = r;
      |            ^~
salesman.cpp:17:20: warning: unused variable 'cr' [-Wunused-variable]
   17 |         ll cl = l, cr = r;
      |                    ^~
salesman.cpp: In function 'void update(ll*, ll, ll)':
salesman.cpp:27:8: warning: unused variable 'check' [-Wunused-variable]
   27 |     ll check = arr[idx];
      |        ^~~~~
salesman.cpp:31:8: warning: unused variable 'check2' [-Wunused-variable]
   31 |     ll check2 = idx;
      |        ^~~~~~

• Subtask 1: 60 / 100