Submission #842035

#	Time	Username	Problem	Language	Result	Execution time	Memory
842035		leeunchong	Salesman (IOI09_salesman)	C++17	100 / 100	382 ms	35900 KiB

salesman

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

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

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

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

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

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

int i;
void query_market(vpi &market)
{
    if(market.size()==0) return;
    sort(market.begin(),market.end());
    vector<int> U,D;
    int sz=market.size();
    for(int i=0;i<sz;i++) {
        int temp=getDP(market[i].first);
        U.push_back(temp),D.push_back(temp);
    }
    for(int i=0;i<sz;i++) {
        if(i!=0) D[i]=max(D[i],D[i-1]-d*(market[i].first-market[i-1].first));
        D[i]+=market[i].second;
    }
    for(int i=sz-1;i>=0;i--) {
        if(i!=sz-1) U[i]=max(U[i],U[i+1]-u*(market[i+1].first-market[i].first));
        U[i]+=market[i].second;
    }
    for(int i=0;i<sz;i++) updateUD(market[i].first,max(U[i],D[i]));
}

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

void input() {
    cin>>n>>u>>d>>s;
    int a, b, c;
    for(i = 0; i<n; i++) {
        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 'int getMax(int*, int, int)':
salesman.cpp:17:13: warning: unused variable 'cl' [-Wunused-variable]
   17 |         int cl = l, cr = r;
      |             ^~
salesman.cpp:17:21: warning: unused variable 'cr' [-Wunused-variable]
   17 |         int cl = l, cr = r;
      |                     ^~

• Subtask 1: 100 / 100