Submission #188800

#	Time	Username	Problem	Language	Result	Execution time	Memory
188800		nickmet2004	Salesman (IOI09_salesman)	C++11	90 / 100	1043 ms	44668 KiB

salesman

#include<bits/stdc++.h>
#define Loc first
#define Prof second

using namespace std;

const int N = 5e5 + 2 , INF = 2e9;

int n , U , D , S;
vector<pair<int , int> > fairs[N];

struct SegTree{
    int T[4 * N];
    void init(){
        fill(T , T + 4 * N , -INF);
    }
    void update(int l , int r , int idx , int v , int pos){
        if(idx < l || r < idx) return;
        if(l == r){
            T[pos] = max(T[pos] , v);
            return;
        }
        int mid = (l + r) >> 1;
        update(l , mid , idx , v , pos * 2);
        update(mid + 1 , r , idx , v , pos * 2 + 1);
        T[pos] = max(T[pos * 2] , T[pos * 2 + 1]);
        return;
    }
    int query(int l , int r , int L , int R , int pos){
        if(r < L || R < l) return -INF;
        if(L <= l && r <= R) {
            return T[pos];
        }
        int mid = (l + r) >> 1;
        int p1 = query(l , mid , L , R , pos * 2);
        int p2 = query(mid + 1 , r , L , R , pos * 2 + 1);
        return max(p1 , p2);
    }
}Up , Down;

void upd(int loc , int best_profit){
    Up.update(1 , N , loc , best_profit - U * loc , 1);
    Down.update(1 , N , loc , best_profit + D * loc , 1);
}
int get(int loc){
    return max(Up.query(1 , N , loc + 1 , N - 1 , 1) + U * loc , Down.query(1 , N , 1 , loc - 1 , 1) - D * loc);
}

void solve(vector<pair<int , int> > &v){
    if(!v.size()) return;
    if(v.size() >= 2) {
        sort(v.begin() , v.end());
    }
    vector<int> Us(v.size());
    vector<int> Ds(v.size());

    for(int i = 0; i < v.size(); ++i){
        Us[i] = Ds[i] = get(v[i].Loc);
    }
    for(int i = 0; i < v.size(); ++i){
        if(!i){Ds[i] += v[i].Prof; continue;}
        Ds[i] = max(Ds[i] , Ds[i - 1] - D * (v[i].Loc - v[i - 1].Loc));
        Ds[i] += v[i].Prof;
    }
    for(int i = v.size() - 1; i >= 0; --i){
        if(i == v.size() - 1) {Us[i] += v[i].Prof; continue;}
        Us[i] = max(Us[i] , Us[i + 1] - U * (v[i + 1].Loc - v[i].Loc));
        Us[i] += v[i].Prof;
    }
    for(int i = 0; i < v.size(); ++i){
        upd(v[i].Loc , max(Us[i] , Ds[i]));
    }
}

int main (){
    ios_base::sync_with_stdio(false);
    scanf("%d%d%d%d" , &n , &U , &D , &S);
    for(int i = 0; i < n; ++i){
        int d , l , pr;
        scanf("%d%d%d" , &d , &l , &pr);
        fairs[d].emplace_back(l , pr);
    }
    Up.init(); Down.init();
    upd(S , 0);
    for(int i = 1; i <= 500001; ++i){
        solve(fairs[i]);
    }
    printf("%d" , max(0 , get(S)));

return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'void solve(std::vector<std::pair<int, int> >&)':
salesman.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); ++i){
                    ~~^~~~~~~~~~
salesman.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); ++i){
                    ~~^~~~~~~~~~
salesman.cpp:66:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i == v.size() - 1) {Us[i] += v[i].Prof; continue;}
            ~~^~~~~~~~~~~~~~~
salesman.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); ++i){
                    ~~^~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d" , &n , &U , &D , &S);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d" , &d , &l , &pr);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 90 / 100