Submission #885199

#TimeUsernameProblemLanguageResultExecution timeMemory
885199MatjazSalesman (IOI09_salesman)C++14
60 / 100
3036 ms41716 KiB
//
//  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;
        
        for (int x=segment.size()-1;x>=0;x--){
            
            for (int y=segment[x].size() - 1; y>=0; y--){
                int i = segment[x][y];
                
                long long best_remaining;
                if (i == N + 1) best_remaining = 0; else best_remaining = -distance(fairs[i].L, S);
                
                if (i<N && fairs[i].T != fairs[i+1].T){
                    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=last_finished;j<=N+1;j++){
                    best_remaining = max(best_remaining, -distance(fairs[i].L,fairs[j].L) + best[j]);
                }
                
                best[i] = fairs[i].M + best_remaining;
                
            }
            last_finished += segment[x][0];
        }
            
            
    }
    
    
    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:165:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |                     for (int j=0;j<V.size();j++){
      |                                  ~^~~~~~~~~
salesman.cpp:177:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |                         for (int k= j+1;k<V.size();k++){
      |                                         ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...