| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 885457 | Matjaz | Salesman (IOI09_salesman) | C++14 | 571 ms | 50424 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;
}
vector<int> new_bests(vector<int> V, vector<int> L, vector<int> M){
int accumulation = 0;
vector<int> best(V.begin(), V.end());
vector<int> downstream_values(V.size());
vector<int> upstream_values(V.size());
vector<int> downstream_accumulation(V.size());
vector<int> upstream_accumulation(V.size());
vector<int> downstream_max(V.size());
vector<int> upstream_max(V.size());
for (int i=downstream_values.size() -1; i>=0;i--){
downstream_values[i] = V[i] + accumulation - distance(L.back(), L[i]);
if (i == downstream_values.size() - 1) downstream_max[i] = downstream_values[i]; else downstream_max[i] = max(downstream_max[i + 1], downstream_values[i]);
downstream_accumulation[i] = accumulation;
accumulation += M[i];
}
accumulation = 0;
for (int i=0;i<upstream_values.size();i++){
upstream_values[i] = V[i] + accumulation - distance(L[0], L[i]);
if (i == 0) upstream_max[0] = upstream_values[0]; else upstream_max[i] = max(upstream_values[i], upstream_max[i-1]);
upstream_accumulation[i] = accumulation;
accumulation += M[i];
}
for (int j=0;j<V.size();j++){
int best_down = downstream_max[j] + distance(L.back(), L[j]) - downstream_accumulation[j];
int best_up = upstream_max[j] + distance(L[0], L[j]) - upstream_accumulation[j];
best[j] = max(best[j], max(best_down, best_up));
}
return best;
}
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;
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 (false){
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 {
upstream.assign(MAXL + 1, INF);
downstream.assign(MAXL + 1, INF);
insert_upstream(S, - S * U);
insert_downstream(S, - (MAXL - S) * D);
for (int x=segment.size()-1;x>=0;x--){
for (int y=segment[x].size() - 1; y>=0; y--){
int i = segment[x][y];
int best_remaining;
if (i == N + 1) best_remaining = 0; else best_remaining = -distance(fairs[i].L, S);
best_remaining = max(best_remaining, best_downstream(fairs[i].L) + (MAXL - fairs[i].L) * D);
best_remaining = max(best_remaining, best_upstream(fairs[i].L) + fairs[i].L * U);
best[i] = fairs[i].M + best_remaining;
}
vector<int> V(segment[x].size());
vector<int> Ls(segment[x].size());
vector<int> Ms(segment[x].size());
for(int y=0;y<segment[x].size();y++){
V[y] = best[segment[x][y]];
Ls[y] = fairs[segment[x][y]].L;
Ms[y] = fairs[segment[x][y]].M;
}
int i = segment[x][0] - 1;
vector<int> updated_bests = new_bests(V, Ls, Ms);
for (int j=0;j<updated_bests.size();j++) best[j + i + 1] = max((long long) updated_bests[j], best[j + i + 1]);
for (int y=segment[x].size()-1;y>=0;y--){
int L = fairs[segment[x][y]].L;
insert_upstream(L, best[segment[x][y]] - L * U);
insert_downstream(L, best[segment[x][y]] - (MAXL - L) * D);
}
}
}
cout << best[0] << endl;
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||