Submission #185479

#	Time	Username	Problem	Language	Result	Execution time	Memory
185479		nickmet2004	Salesman (IOI09_salesman)	C++11	0 / 100	387 ms	65540 KiB

salesman

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

using namespace std;

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

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

struct SegTree{
    int T[4 * N];
    void init(){
        for(int i = 0; i < 4 * N; ++i){
            T[i] = -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;
    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);
    //cin.tie(0);
    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]);
        if(fairs[i].size() == 0) continue;
        sort(fairs[i].begin() , fairs[i].end());
        vector<int> Us(fairs[i].size());
        vector<int> Ds(fairs[i].size());

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

return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:93:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < fairs[i].size(); ++j){
                        ~~^~~~~~~~~~~~~~~~~
salesman.cpp:96:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < fairs[i].size(); ++j){
                        ~~^~~~~~~~~~~~~~~~~
salesman.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i == fairs[i].size() - 1) {Us[j] += fairs[i][j].Prof; continue;}
                ~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:106:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < fairs[i].size(); ++j){
                        ~~^~~~~~~~~~~~~~~~~
salesman.cpp:78: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:81: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: 0 / 100