Submission #871598

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
871598	2023-11-11T07:11:05 Z	Matjaz	Salesman (IOI09_salesman)	C++14	19 / 100	3000 ms	22868 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	4 ms	348 KB	Output is correct
5	Correct	40 ms	552 KB	Output is correct
6	Correct	651 ms	1336 KB	Output is correct
7	Execution timed out	3043 ms	2648 KB	Time limit exceeded
8	Execution timed out	3018 ms	4776 KB	Time limit exceeded
9	Execution timed out	3075 ms	6660 KB	Time limit exceeded
10	Execution timed out	3024 ms	13136 KB	Time limit exceeded
11	Execution timed out	3063 ms	14040 KB	Time limit exceeded
12	Execution timed out	3039 ms	17492 KB	Time limit exceeded
13	Execution timed out	3058 ms	17748 KB	Time limit exceeded
14	Execution timed out	3054 ms	22868 KB	Time limit exceeded
15	Execution timed out	3040 ms	22096 KB	Time limit exceeded
16	Execution timed out	3038 ms	22044 KB	Time limit exceeded
17	Correct	0 ms	344 KB	Output is correct
18	Incorrect	1 ms	348 KB	Output isn't correct
19	Incorrect	1 ms	348 KB	Output isn't correct
20	Incorrect	7 ms	528 KB	Output isn't correct
21	Incorrect	7 ms	348 KB	Output isn't correct
22	Incorrect	24 ms	600 KB	Output isn't correct
23	Incorrect	18 ms	600 KB	Output isn't correct
24	Incorrect	27 ms	600 KB	Output isn't correct
25	Execution timed out	3052 ms	4516 KB	Time limit exceeded
26	Execution timed out	3019 ms	8528 KB	Time limit exceeded
27	Execution timed out	3064 ms	14420 KB	Time limit exceeded
28	Execution timed out	3099 ms	15140 KB	Time limit exceeded
29	Execution timed out	3039 ms	20568 KB	Time limit exceeded
30	Execution timed out	3047 ms	21332 KB	Time limit exceeded