Submission #885204

#	Time	Username	Problem	Language	Result	Execution time	Memory
885204		Matjaz	Salesman (IOI09_salesman)	C++14	90 / 100	3041 ms	41712 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;
    }
    
    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);
    }
    
    
    
    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 {
        
        int last_finished = N + 2;
        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<long long> 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;
            
            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];
                }
            }
            
            last_finished = segment[x][0];
            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 'int main()':
salesman.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i=1;i<fairs.size();i++) if (fairs[i].T == fairs[i-1].T){
      |                  ~^~~~~~~~~~~~~
salesman.cpp:168:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |             for(int y=0;y<segment[x].size();y++){
      |                         ~^~~~~~~~~~~~~~~~~~
salesman.cpp:176:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |             for (int j=0;j<V.size();j++){
      |                          ~^~~~~~~~~
salesman.cpp:188:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |                 for (int k= j+1;k<V.size();k++){
      |                                 ~^~~~~~~~~
salesman.cpp:143:13: warning: variable 'last_finished' set but not used [-Wunused-but-set-variable]
  143 |         int last_finished = N + 2;
      |             ^~~~~~~~~~~~~

• Subtask 1: 90 / 100