Submission #885137

#	Time	Username	Problem	Language	Result	Execution time	Memory
885137		Matjaz	Salesman (IOI09_salesman)	C++14	14 / 100	3080 ms	16560 KiB

salesman

//
//  SalesmanIOI2009multiple.cpp
//  
//
//  Created by Matjaz Leonardis on 09/12/2023.
//

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> L;
vector<int> T;
vector<int> M;
 
int N,D,U,S;
 
long long distance(int L1, int L2){
    if (L1 > L2) return D * (L1 - L2);
    return U * (L2 - L1);
}
 
 
int main(){
    
    cin >> N >> D >> U >> S;
    
    vector<pair<int, pair<int,int> > > tmp(N+2);
    for (int i=0;i<N;i++){
        cin >> tmp[i].first >> tmp[i].second.first >> tmp[i].second.second;
    }
    tmp[N] = make_pair(-1, make_pair(S, 0));
    tmp[N+1] = make_pair(500001, make_pair(S, 0));
    sort(tmp.begin(), tmp.end());
    
    T.assign(N+2, 0);
    L.assign(N+2, 0);
    M.assign(N+2, 0);
    for (int i=0;i<N+2;i++){
        L[i] = tmp[i].second.first;
        M[i] = tmp[i].second.second;
        T[i] = tmp[i].first;
    }
    
    vector<long long> best(N+2, 0);
    
    for (int i=N+1;i>=0;i--){
        
        long long best_remaining;
        if (i == N + 1) best_remaining = 0; else best_remaining = -distance(L[i], S);
        
        if (T[i] != T[i+1] && i != N){
            vector<int> V;
            vector<int> Ls;
            vector<int> Ms;
            int index = i + 1;
            while (T[i+1] == T[index]){
                V.push_back(best[index]);
                Ls.push_back(L[index]);
                Ms.push_back(M[index]);
                index++;
            }
            
            for (int j=0;j<V.size();j++){
                
                int accumulation = M[j];
                
                for (int k=j-1;k>=0;k--){
                    best[j + i + 1] = max(best[j + i +1], V[k] + accumulation - distance(L[j], L[k]));
                    accumulation += M[k];
                    
                }
                
                accumulation = M[j];
                
                for (int k= j+1;k<V.size();k++){
                    best[j + i + 1] = max(best[j + i +1], V[k] + accumulation - distance(L[j], L[k]));
                    accumulation += M[k];
                }
            }
        }
        
        for (int j=i+1;j<N+1;j++){
            if (T[j] == T[i]) continue;
            best_remaining = max(best_remaining, -distance(L[i],L[j]) + best[j]);
        }
        
        best[i] = M[i] + best_remaining;
    }
    
    cout << best[0] << endl;
    
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for (int j=0;j<V.size();j++){
      |                          ~^~~~~~~~~
salesman.cpp:78:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                 for (int k= j+1;k<V.size();k++){
      |                                 ~^~~~~~~~~

• Subtask 1: 14 / 100