# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
885145 | Matjaz | Salesman (IOI09_salesman) | C++14 | 3073 ms | 13968 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//
// 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);
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;
}
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 {
for (int i=N+1;i>=0;i--){
long long best_remaining;
if (i == N + 1) best_remaining = 0; else best_remaining = -distance(fairs[i].L, S);
if (fairs[i].T != fairs[i+1].T && i < N){
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=i+1;j<N+1;j++){
if (fairs[j].T == fairs[i].T) continue;
best_remaining = max(best_remaining, -distance(fairs[i].L,fairs[j].L) + best[j]);
}
best[i] = fairs[i].M + best_remaining;
}
}
cout << best[0] << endl;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |