Submission #504010

#	Time	Username	Problem	Language	Result	Execution time	Memory
504010		79brue	Salesman (IOI09_salesman)	C++14	100 / 100	702 ms	17380 KiB

salesman

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Market{
    int day; int loc; int w;

    bool operator<(const Market &r)const{
        return day == r.day ? loc < r.loc : day < r.day;
    }
};

struct segTree{
    int tree[1048578];

    void init(int i, int l, int r){
        if(l==r){
            tree[i] = -2e9;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m), init(i*2+1, m+1, r);
        tree[i] = -2e9;
    }

    void update(int i, int l, int r, int x, int v){
        if(l==r){
            tree[i] = max(tree[i], v);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    int query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return -2e9;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} treeU, treeD;

int n; int u, d; int s;
Market arr[500002];

int main(){
    scanf("%d %d %d %d", &n, &u, &d, &s);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d", &arr[i].day, &arr[i].loc, &arr[i].w);
    }
    sort(arr+1, arr+n+1);

    const int MAX = 500001;
    treeU.init(1, 1, MAX), treeD.init(1, 1, MAX);
    treeU.update(1, 1, MAX, s, -u*s);
    treeD.update(1, 1, MAX, s, d*s);
    for(int i=1; i<=n; i++){
        int j = i;
        while(arr[j+1].day == arr[i].day) j++;
        if(i==j){
            int val = max(treeU.query(1, 1, MAX, arr[i].loc, MAX) + arr[i].loc * u,
                         treeD.query(1, 1, MAX, 1, arr[i].loc) - arr[i].loc * d) + arr[i].w;
            treeU.update(1, 1, MAX, arr[i].loc, val-u*arr[i].loc);
            treeD.update(1, 1, MAX, arr[i].loc, val+d*arr[i].loc);
            continue;
        }

        vector<pair<int, int> > vec;
        int btmp = -2e9;
        for(int x=i; x<=j; x++){
            int val = max(treeU.query(1, 1, MAX, arr[x].loc, MAX) + arr[x].loc * u,
                         treeD.query(1, 1, MAX, 1, arr[x].loc) - arr[x].loc * d) + arr[x].w;
            val = max(val, btmp - arr[x].loc * d + arr[x].w);
            vec.push_back(make_pair(arr[x].loc, val));
            btmp = max(btmp, val + arr[x].loc * d);
        }
        for(int x=j; x>=i; x--){
            int val = max(treeU.query(1, 1, MAX, arr[x].loc, MAX) + arr[x].loc * u,
                         treeD.query(1, 1, MAX, 1, arr[x].loc) - arr[x].loc * d) + arr[x].w;
            treeU.update(1, 1, MAX, arr[x].loc, val-u*arr[x].loc);
            treeD.update(1, 1, MAX, arr[x].loc, val+d*arr[x].loc);
        }
        for(auto p: vec){
            treeU.update(1, 1, MAX, p.first, p.second-u*p.first);
            treeD.update(1, 1, MAX, p.first, p.second+d*p.first);
        }
        i=j;
    }

    int ans = max(treeU.query(1, 1, MAX, s, MAX) + s*u,
              treeD.query(1, 1, MAX, 1, s) - s*d);
    printf("%d", ans);
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d %d %d %d", &n, &u, &d, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d %d %d", &arr[i].day, &arr[i].loc, &arr[i].w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100