Submission #885463

#	Time	Username	Problem	Language	Result	Execution time	Memory
885463		Matjaz	Salesman (IOI09_salesman)	C++14	100 / 100	538 ms	41532 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;
}

vector<int> new_bests(vector<int> V, vector<int> L, vector<int> M){
    
    int accumulation = 0;
    
    vector<int> best(V.begin(), V.end());
    
    vector<int> downstream_values(V.size());
    vector<int> upstream_values(V.size());
    vector<int> downstream_accumulation(V.size());
    vector<int> upstream_accumulation(V.size());
    vector<int> downstream_max(V.size());
    vector<int> upstream_max(V.size());
    
     
    
    for (int i=downstream_values.size() -1; i>=0;i--){
        downstream_values[i] = V[i] + accumulation - distance(L.back(), L[i]);
        downstream_accumulation[i] = accumulation;
        accumulation += M[i];
    }
    
    downstream_max[0] = downstream_values[0];
    for (int i=1;i<downstream_values.size();i++) downstream_max[i] = max(downstream_max[i-1], downstream_values[i]);
    
    accumulation = 0;
    
    for (int i=0;i<upstream_values.size();i++){
        upstream_values[i] = V[i] + accumulation - distance(L[0], L[i]);
        upstream_accumulation[i] = accumulation;
        accumulation += M[i];
    }
    
    upstream_max.back() = upstream_values.back();
    for (int i=upstream_values.size() - 2;i>=0;i--) upstream_max[i] = max(upstream_max[i+1], upstream_values[i]);
    
    for (int j=0;j<V.size();j++){
        
        int best_down = downstream_max[j] + distance(L.back(), L[j]) - downstream_accumulation[j];
        
        int best_up = upstream_max[j] + distance(L[0], L[j]) - upstream_accumulation[j];
        
        best[j] = max(best[j], max(best_down, best_up));
    }
    
    return best;
    
}


int main(){
    
    cin >> N >> D >> U >> S;
    vector<fair> fairs(N+2);
    
    MAXL = S;
    
    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;
    
    vector<vector<int> > segment(1);
    segment[0].push_back(0);
    for (int i=1;i<=N+1;i++){
        if (fairs[i].T != fairs[i-1].T){
            segment.push_back(vector<int> ());
        }
        segment.back().push_back(i);
    }
    
    upstream.assign(MAXL + 1, INF);
    downstream.assign(MAXL + 1, INF);
    insert_upstream(S, - S * U);
    insert_downstream(S, - (MAXL - S) * D);
    
    for (int x=segment.size()-1;x>=0;x--){
        
        for (int y=segment[x].size() - 1; y>=0; y--){
            int i = segment[x][y];
            
            int best_remaining;
            if (i == N + 1) best_remaining = 0; else best_remaining = -distance(fairs[i].L, S);
            
            best_remaining = max(best_remaining, best_downstream(fairs[i].L) + (MAXL - fairs[i].L) * D);
            best_remaining = max(best_remaining, best_upstream(fairs[i].L) + fairs[i].L * U);
            
            best[i] = fairs[i].M + best_remaining;
            
        }
        
        vector<int> V(segment[x].size());
        vector<int> Ls(segment[x].size());
        vector<int> Ms(segment[x].size());

        for(int y=0;y<segment[x].size();y++){
            V[y] = best[segment[x][y]];
            Ls[y] = fairs[segment[x][y]].L;
            Ms[y] = fairs[segment[x][y]].M;
        }
        
        int i = segment[x][0] - 1;
        
        vector<int> updated_bests = new_bests(V, Ls, Ms);
        
        for (int j=0;j<updated_bests.size();j++) best[j + i + 1] = max((long long) updated_bests[j], best[j + i + 1]);
        
        for (int y=segment[x].size()-1;y>=0;y--){
            int L = fairs[segment[x][y]].L;
            insert_upstream(L, best[segment[x][y]] - L * U);
            insert_downstream(L, best[segment[x][y]] - (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()){
      |            ~~^~~~~~~~~~~~~~~~~
salesman.cpp: In function 'std::vector<int> new_bests(std::vector<int>, std::vector<int>, std::vector<int>)':
salesman.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i=1;i<downstream_values.size();i++) downstream_max[i] = max(downstream_max[i-1], downstream_values[i]);
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i=0;i<upstream_values.size();i++){
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int j=0;j<V.size();j++){
      |                  ~^~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:179:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |         for(int y=0;y<segment[x].size();y++){
      |                     ~^~~~~~~~~~~~~~~~~~
salesman.cpp:189:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |         for (int j=0;j<updated_bests.size();j++) best[j + i + 1] = max((long long) updated_bests[j], best[j + i + 1]);
      |                      ~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100