oj.uz

답안 #842035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
842035 2023-09-02T10:26:28 Z leeunchong Salesman (IOI09_salesman) C++17
100 / 100
 382 ms 35900 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 19800 KB Output is correct
2 Correct 5 ms 19800 KB Output is correct
3 Correct 5 ms 20004 KB Output is correct
4 Correct 6 ms 20056 KB Output is correct
5 Correct 7 ms 20056 KB Output is correct
6 Correct 17 ms 20568 KB Output is correct
7 Correct 34 ms 21336 KB Output is correct
8 Correct 72 ms 23120 KB Output is correct
9 Correct 107 ms 24656 KB Output is correct
10 Correct 175 ms 29408 KB Output is correct
11 Correct 246 ms 29400 KB Output is correct
12 Correct 274 ms 32528 KB Output is correct
13 Correct 276 ms 32524 KB Output is correct
14 Correct 325 ms 35416 KB Output is correct
15 Correct 323 ms 35664 KB Output is correct
16 Correct 382 ms 35900 KB Output is correct
17 Correct 5 ms 19800 KB Output is correct
18 Correct 5 ms 19800 KB Output is correct
19 Correct 6 ms 19800 KB Output is correct
20 Correct 6 ms 20056 KB Output is correct
21 Correct 7 ms 20056 KB Output is correct
22 Correct 7 ms 20060 KB Output is correct
23 Correct 7 ms 20056 KB Output is correct
24 Correct 7 ms 20056 KB Output is correct
25 Correct 54 ms 21312 KB Output is correct
26 Correct 92 ms 22488 KB Output is correct
27 Correct 153 ms 24364 KB Output is correct
28 Correct 188 ms 24292 KB Output is correct
29 Correct 222 ms 24848 KB Output is correct
30 Correct 234 ms 26136 KB Output is correct