제출 #842032

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842032		leeunchong	Salesman (IOI09_salesman)	C++17	60 / 100	479 ms	43604 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("%lld %lld %lld %lld",&n,&u,&d,&s);
    ll a, b, c;
    for(int x = 0; x<n; x++) {
        scanf("%lld %lld %lld",&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("%lld",getDP(s));
}

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

컴파일 시 표준 에러 (stderr) 메시지

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("%lld %lld %lld %lld",&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("%lld %lld %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100