| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 885145 |
2023-12-09T04:27:41 Z |
Matjaz |
Salesman (IOI09_salesman) |
C++14 |
|
3000 ms |
13968 KB |
//
// 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
salesman.cpp: In function 'void insert_downstream(int, int)':
salesman.cpp:37:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | while (x < downstream.size()){
| ~~^~~~~~~~~~~~~~~~~~~
salesman.cpp: In function 'void insert_upstream(int, int)':
salesman.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | while (x < upstream.size()){
| ~~^~~~~~~~~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int i=1;i<fairs.size();i++) if (fairs[i].T == fairs[i-1].T){
| ~^~~~~~~~~~~~~
salesman.cpp:145:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int j=0;j<V.size();j++){
| ~^~~~~~~~~
salesman.cpp:157:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for (int k= j+1;k<V.size();k++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
348 KB |
Output is correct |
| 6 |
Correct |
16 ms |
4520 KB |
Output is correct |
| 7 |
Correct |
39 ms |
5104 KB |
Output is correct |
| 8 |
Correct |
76 ms |
6224 KB |
Output is correct |
| 9 |
Correct |
118 ms |
7048 KB |
Output is correct |
| 10 |
Correct |
209 ms |
10068 KB |
Output is correct |
| 11 |
Correct |
230 ms |
10100 KB |
Output is correct |
| 12 |
Correct |
289 ms |
12040 KB |
Output is correct |
| 13 |
Correct |
307 ms |
12112 KB |
Output is correct |
| 14 |
Correct |
384 ms |
13968 KB |
Output is correct |
| 15 |
Correct |
352 ms |
13968 KB |
Output is correct |
| 16 |
Correct |
384 ms |
13908 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
2 ms |
348 KB |
Output is correct |
| 20 |
Correct |
7 ms |
348 KB |
Output is correct |
| 21 |
Correct |
7 ms |
348 KB |
Output is correct |
| 22 |
Correct |
25 ms |
348 KB |
Output is correct |
| 23 |
Correct |
21 ms |
536 KB |
Output is correct |
| 24 |
Correct |
28 ms |
600 KB |
Output is correct |
| 25 |
Execution timed out |
3035 ms |
2360 KB |
Time limit exceeded |
| 26 |
Execution timed out |
3050 ms |
4532 KB |
Time limit exceeded |
| 27 |
Execution timed out |
3073 ms |
7728 KB |
Time limit exceeded |
| 28 |
Execution timed out |
3049 ms |
7604 KB |
Time limit exceeded |
| 29 |
Execution timed out |
3027 ms |
10400 KB |
Time limit exceeded |
| 30 |
Execution timed out |
3065 ms |
10960 KB |
Time limit exceeded |
