/**
* Solution to IOI 2009 problem "salesman"
*
* We use a C++ set to store the list of currently "active" fairs,
* where an active fair is one that has a better profit than by
* visiting the fair than reaching the same location from some
* other fair. We then process the fairs in order of the time at
* which they occur, using our active set to find the best fair
* to come from in order to visit each new successive fair, and
* updating the active set with the new fair afterwards.
*
* For fairs on the same day, we note that the most efficient
* way of visiting these is to pick one as a starting point and
* then visit fairs in a single direction. We test both the
* upstream and downstream directions, and for each fair decide
* whether it is better to go directly to this fair or to come
* from the previous fair opposite to the direction in which
* we are travelling.
*
* Carl Hultquist, [email protected]
*/
#include <iostream>
#include <cassert>
#include <set>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
#define MAX_N 500000
#define MAX_D_U 10
#define MAX_S 500001
#define MAX_T 500000
#define MAX_L 500001
#define MAX_M 4000
int n, d, u, s;
// Class for storing all the things we want to associate with a fair
typedef struct fair
{
int t, l, m;
int best;
// Used for traversing upstream and downstream when fairs occur
// on the same day.
int baseBest;
int curBest;
// Order fairs first according to time, and secondly according
// to their location (which makes the upstream and downstream
// traversals much easier).
bool operator <(const fair &f) const
{
if (t < f.t)
return true;
else if (t == f.t && l < f.l)
return true;
else
return false;
}
} fair;
// For our set, we want to order fairs by location only, so have
// a special comparator for this.
struct location_less
{
bool operator ()(const fair &x, const fair &y)
{
return x.l < y.l;
}
};
vector<fair> fairs;
set<fair, location_less> activeFairs;
/**
* Computes the cost of travelling between two points on the river.
*/
double travelCost(double from, double to)
{
if (from < to)
return (to - from) * d;
else
return (from - to) * u;
}
/**
* Queries for the best profit that we can expect to earn when
* visiting fair i directly from some fair that occurred on a
* previous day.
*
* We find the active fairs that occur to the left and right of
* this one along the river -- it is fairly easy to show that our
* optimal predecessor must be one of these fairs. Then we pick
* the one which gives us a greater profit.
*/
int query(int i)
{
set<fair, location_less>::iterator low = activeFairs.lower_bound(fairs[i]);
set<fair, location_less>::iterator high = low;
if (low != activeFairs.begin())
low--;
if (high == activeFairs.end())
high--;
return max(low->best - travelCost(low->l, fairs[i].l),
high->best - travelCost(high->l, fairs[i].l)) + fairs[i].m;
}
/**
* Updates our active fairs set with the given fair. Care must be
* taken to ensure that this fair is actually active (if all fairs
* are on distinct days then it will be, but if there are several on
* the same day then there may be a better path to this location on
* the river via some other fair).
*/
void update(int i)
{
// Insert by default, we will remove it later if we need to.
activeFairs.insert(fairs[i]);
set<fair, location_less>::iterator thisFair = activeFairs.lower_bound(fairs[i]);
set<fair, location_less>::iterator cur = thisFair;
// Check upstream fairs
while (cur != activeFairs.begin())
{
cur--;
// Check if the fair we have just added is covered by the
// previous fair in the set.
if (cur->best - travelCost(cur->l, thisFair->l) >= thisFair->best)
{
// Yes, so remove and return
activeFairs.erase(thisFair);
return;
}
// Check if the fair we have just added covers the previous
// fair in the set.
if (thisFair->best - travelCost(thisFair->l, cur->l) < cur->best)
// No, so stop removing non-active fairs
break;
// Remove the fair that is covered by our recently added one,
// and which is thus no longer active.
activeFairs.erase(cur);
cur = thisFair;
}
// Check downstream fairs
cur = thisFair;
cur++;
while (cur != activeFairs.end())
{
// Check if the fair we have just added is covered by the
// next fair in the set.
if (cur->best - travelCost(cur->l, thisFair->l) >= thisFair->best)
{
// Yes, so remove and return
activeFairs.erase(thisFair);
return;
}
// Check if the fair we have just added covers the next
// fair in the set.
if (thisFair->best - travelCost(thisFair->l, cur->l) < cur->best)
break;
// Remove the fair that is covered by our recently added one,
// and which is thus no longer active.
activeFairs.erase(cur);
cur = thisFair;
cur++;
}
}
int main()
{
scanf("%d %d %d %d", &n, &u, &d, &s);
assert(1 <= n && n <= MAX_N);
assert(1 <= d && d <= MAX_D_U);
assert(1 <= u && u <= MAX_D_U);
assert(1 <= s && s <= MAX_S);
fairs.resize(n + 2);
int maxT = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d %d %d", &fairs[i].t, &fairs[i].l, &fairs[i].m);
assert(1 <= fairs[i].t && fairs[i].t <= MAX_T);
assert(1 <= fairs[i].l && fairs[i].l <= MAX_L);
assert(1 <= fairs[i].m && fairs[i].m <= MAX_M);
maxT = max(maxT, fairs[i].t);
}
// Create a dummy fairs for the salesman's home at the beginning,
// and also one at the end
fairs[0].l = s;
fairs[0].best = 0;
fairs[0].t = -1;
fairs[n + 1].l = s;
fairs[n + 1].m = 0;
fairs[n + 1].t = maxT + 1;
sort(fairs.begin(), fairs.end());
// At the beginning, only fair 0 (the salesman's home) is active
activeFairs.insert(fairs[0]);
for (int i = 1; i <= n; i++)
{
// Check to see if we have multiple fairs on the same day
if (i == n || fairs[i].t != fairs[i + 1].t)
{
// No, so just do the simple approach of querying for
// the best fair to come from in order to reach this
// one, and update our data structure.
fairs[i].best = query(i);
update(i);
}
else
{
// Yes, there are multiple fairs happening on this day. We need
// to choose the best way of picking which of these fairs to
// visit.
int first = i;
while (i <= n && fairs[i].t == fairs[first].t)
i++;
i--;
int last = i;
// First, find the cheapest way of reaching each fair on this
// day if we visit no other fairs on the same day.
for (int j = first; j <= last; j++)
{
fairs[j].baseBest = query(j);
fairs[j].best = fairs[j].baseBest;
}
// Now visit each of the fairs in both an upstream and
// downstream direction, in each case seeing if it was
// better to come via the previous fair.
fairs[first].curBest = fairs[first].baseBest;
for (int j = first + 1; j <= last; j++)
{
// See if it is better to come from the previous
// fair.
int profit = fairs[j - 1].curBest - travelCost(fairs[j - 1].l, fairs[j].l) + fairs[j].m;
if (profit > fairs[j].baseBest)
fairs[j].curBest = profit;
else
fairs[j].curBest = fairs[j].baseBest;
if (fairs[j].curBest > fairs[j].best)
fairs[j].best = fairs[j].curBest;
}
// And upstream. Don't forget to start off with the base
// value of visiting this fair directly (otherwise we will
// use values fro the downstream pass, which will be
// confusing).
fairs[last].curBest = fairs[last].baseBest;
for (int j = last - 1; j >= first; j--)
{
// See if it is better to come from the previous
// fair.
int profit = fairs[j + 1].curBest - travelCost(fairs[j + 1].l, fairs[j].l) + fairs[j].m;
if (profit > fairs[j].baseBest)
fairs[j].curBest = profit;
else
fairs[j].curBest = fairs[j].baseBest;
if (fairs[j].curBest > fairs[j].best)
fairs[j].best = fairs[j].curBest;
}
// Update our query structure for all of these fairs, and
// see if there is a better way home from any of them.
for (int j = first; j <= last; j++)
update(j);
}
}
int best = query(n + 1);
// Check that our profit is positive; if not then output 0
// (indicating that the salesman simply stays at home for the
// year).
cout << (best < 0 ? 0 : best) << endl;
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:185:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &n, &u, &d, &s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:196:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &fairs[i].t, &fairs[i].l, &fairs[i].m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
408 KB |
Output is correct |
| 4 |
Correct |
3 ms |
408 KB |
Output is correct |
| 5 |
Correct |
6 ms |
724 KB |
Output is correct |
| 6 |
Correct |
20 ms |
932 KB |
Output is correct |
| 7 |
Correct |
43 ms |
1688 KB |
Output is correct |
| 8 |
Correct |
86 ms |
2968 KB |
Output is correct |
| 9 |
Correct |
130 ms |
4120 KB |
Output is correct |
| 10 |
Correct |
297 ms |
9220 KB |
Output is correct |
| 11 |
Correct |
368 ms |
9220 KB |
Output is correct |
| 12 |
Correct |
378 ms |
10200 KB |
Output is correct |
| 13 |
Correct |
388 ms |
10200 KB |
Output is correct |
| 14 |
Correct |
446 ms |
12516 KB |
Output is correct |
| 15 |
Correct |
508 ms |
15076 KB |
Output is correct |
| 16 |
Correct |
498 ms |
15076 KB |
Output is correct |
| 17 |
Correct |
2 ms |
15076 KB |
Output is correct |
| 18 |
Correct |
3 ms |
15076 KB |
Output is correct |
| 19 |
Correct |
4 ms |
15076 KB |
Output is correct |
| 20 |
Correct |
4 ms |
15076 KB |
Output is correct |
| 21 |
Correct |
6 ms |
15076 KB |
Output is correct |
| 22 |
Correct |
5 ms |
15076 KB |
Output is correct |
| 23 |
Correct |
4 ms |
15076 KB |
Output is correct |
| 24 |
Correct |
6 ms |
15076 KB |
Output is correct |
| 25 |
Correct |
61 ms |
15076 KB |
Output is correct |
| 26 |
Correct |
177 ms |
15076 KB |
Output is correct |
| 27 |
Correct |
253 ms |
15076 KB |
Output is correct |
| 28 |
Correct |
352 ms |
15076 KB |
Output is correct |
| 29 |
Correct |
478 ms |
15076 KB |
Output is correct |
| 30 |
Correct |
345 ms |
15076 KB |
Output is correct |
