Submission #885147

#	Time	Username	Problem	Language	Result	Execution time	Memory
885147		Matjaz	Salesman (IOI09_salesman)	C++14	85 / 100	3100 ms	14244 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);
    
    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;
    
    bool distinctTimes = true;
    for (int i=1;i<fairs.size();i++) if (fairs[i].T == fairs[i-1].T){
        distinctTimes = false;
        break;
    }
    
    if (distinctTimes){
        
        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);
        }
        
    } else {
        
        for (int i=N+1;i>=0;i--){
            
            long long best_remaining;
            if (i == N + 1) best_remaining = 0; else best_remaining = -distance(fairs[i].L, S);
            
            if (fairs[i].T != fairs[i+1].T && i < N){
                vector<long long> V;
                vector<int> Ls;
                vector<int> Ms;
                int index = i + 1;
                while (fairs[i + 1].T == fairs[index].T){
                    V.push_back(best[index]);
                    Ls.push_back(fairs[index].L);
                    Ms.push_back(fairs[index].M);
                    index++;
                }
                
                for (int j=0;j<V.size();j++){
                    
                    long long accumulation = Ms[j];
                    
                    for (int k=j-1;k>=0;k--){
                        best[j + i + 1] = max(best[j + i +1], V[k] + accumulation - distance(Ls[j], Ls[k]));
                        accumulation += Ms[k];
                        
                    }
                    
                    accumulation = Ms[j];
                    
                    for (int k= j+1;k<V.size();k++){
                        best[j + i + 1] = max(best[j + i +1], V[k] + accumulation - distance(Ls[j], Ls[k]));
                        accumulation += Ms[k];
                    }
                }
            }
            
            for (int j=i+1;j<N+1;j++){
                if (fairs[j].T == fairs[i].T) continue;
                best_remaining = max(best_remaining, -distance(fairs[i].L,fairs[j].L) + best[j]);
            }
            
            best[i] = fairs[i].M + best_remaining;
        }
    }
    
    
    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 'int main()':
salesman.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i=1;i<fairs.size();i++) if (fairs[i].T == fairs[i-1].T){
      |                  ~^~~~~~~~~~~~~
salesman.cpp:147:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |                 for (int j=0;j<V.size();j++){
      |                              ~^~~~~~~~~
salesman.cpp:159:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |                     for (int k= j+1;k<V.size();k++){
      |                                     ~^~~~~~~~~

• Subtask 1: 85 / 100