Submission #879229

#	Time	Username	Problem	Language	Result	Execution time	Memory
879229		Matjaz	Salesman (IOI09_salesman)	C++14	60 / 100	372 ms	22928 KiB

salesman

//
//  IOI2009Salesman.cpp
//  
//
//  Created by Matjaz Leonardis on 11/11/2023.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct fair{
    int T;
    int L;
    int M;
    bool operator<(const fair& other) const {
        return T < other.T || (T == other.T && L < other.L);
    }
};

int N,D,U,S;

int INF = (1<<31);
int MAXL = 0;

long long distance(int L1, int L2){
    if (L1 > L2) return D * (L1 - L2);
    return U * (L2 - L1);
}

vector<int> upstream;
vector<int> downstream;

void insert_downstream(int x, int v){
    while (x < downstream.size()){
        downstream[x] = max(downstream[x], v);
        x += x & (-x);
    }
}

void insert_upstream(int x, int v){
    x = MAXL - x + 1;
    while (x < upstream.size()){
        upstream[x] = max(upstream[x], v);
        x += x & (-x);
    }
}

int best_downstream(int x){
    
    int res = INF;
    
    while (x > 0){
        res = max(res, downstream[x]);
        x -= x & (-x);
    }
    
    return res;
}

int best_upstream(int x){
    x = MAXL - x + 1;
    int res = INF;
    
    while (x > 0){
        res = max(res, upstream[x]);
        x -= x & (-x);
    }
    
    return res;
}


int main(){
    
    cin >> N >> D >> U >> S;
    vector<fair> fairs(N+2);
    
    for (int i=0;i<N;i++){
        cin >> fairs[i].T >> fairs[i].L >> fairs[i].M;
        MAXL = max(MAXL, fairs[i].L);
    }
    
    fair start = {-1, S, 0};
    fair end = {500001, S, 0};
    
    fairs[N] = start;
    fairs[N+1] = end;
    sort(fairs.begin(), fairs.end());
    
    vector<long long> best(N+2, 0);
    best[N + 1] = 0;
    
    upstream.assign(MAXL + 1, INF);
    downstream.assign(MAXL + 1, INF);
    insert_upstream(S, - S * U);
    insert_downstream(S, - (MAXL - S) * D);
    
    for (int i=N;i>=0;i--){
        
        int best_remaining;
        best_remaining = - distance(fairs[i].L, S);
        int L = fairs[i].L;
        
        // Get best choice upstream and downstream adjusted for current location
        
        best_remaining = max(best_remaining, best_downstream(L) + (MAXL - L) * D);
        best_remaining = max(best_remaining, best_upstream(L) + L * U);
        
        best[i] = fairs[i].M + best_remaining;
        
        insert_upstream(L, best[i] - L * U);
        insert_downstream(L, best[i] - (MAXL - L) * D);
    }
    
    cout << best[0] << endl;
    
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'void insert_downstream(int, int)':
salesman.cpp:37:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while (x < downstream.size()){
      |            ~~^~~~~~~~~~~~~~~~~~~
salesman.cpp: In function 'void insert_upstream(int, int)':
salesman.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while (x < upstream.size()){
      |            ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100