Submission #871598

#	Time	Username	Problem	Language	Result	Execution time	Memory
871598		Matjaz	Salesman (IOI09_salesman)	C++14	19 / 100	3099 ms	22868 KiB

salesman

//
//  IOI2009Salesman.cpp
//  
//
//  Created by Matjaz Leonardis on 11/11/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());
    
    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;
    }
    
    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);
        
        for (int j=i+1;j<N+1;j++){
            best_remaining = max(best_remaining, -distance(L[i],L[j]) + best[j]);
        }
        
        best[i] = M[i] + best_remaining;
    }
    
    cout << best[0] << endl;
    
    return 0;
}

• Subtask 1: 19 / 100