In Burger Town new burger restaurants will be opened! Concretely, restaurants will open in days, while restaurant will be opened on day and will be located at . The town should be imagined as an one dimensional line in which every object's location can be described by the coordinate.
Tim has just recently arrived the town after a very bad result in a programming contest. Thus he wants to cheer himself up by starting a trip to try out some new burgers.
Every burger restaurant is associated with two integers and . If Tim eats a burger from , then his happiness will increase by , which can also be negative, depending on the deliciousness of the burger. On the other hand, if Tim looks through the window of an opened restaurant , from which he will not eat a burger, then his happiness decreases by , since Tim gets sad by only seeing the burgers.
Tim's journey can start from any day at the burger restaurant and eats a burger from there. On each subsequent day , Tim has the following options:
- Stay at the previous restaurant .
- Or go to the new restaurant to eat a burger from there.
If he decides for the latter option, then on the path from to he will look through all the windows that are on his path and maybe lose some happiness. Concretely, if , then he will look through the window of everyopened restaurant , having . Similar for the case .
Since Tim is a very good friend of yours you should help him finding a trip that will maximize his happiness. If he should stay at home since no trip would cheer him up, then print
0.
Note: Tim's happiness is 0 at the beginning of the trip and is allowed to be negative throughout the time.
Input Format
will be given on the first line, then lines will follow, describing the restaurants numbered from 1 to accordingly. Restaurant will be described by , and separated by a single space.
Output Format
Output the maximium happiness on one line.
Constraints
- and no two restaurants will have the same coordinates.
Sample Input
3
2 -5 1
1 5 1
3 5 1
Sample Output
8
Sample Input
4
4 10 0
1 -5 0
3 0 10
2 10 0
Sample Output
15
Sample Input
3
1 -1 0
2 -2 0
3 -3 0
Sample Output
0
First testcase: His trip starts on day 2 at restaurant 2 located at . He gains happiness points there by eating a burger. On the next day he goes from restaurant 2 to 3, but will look through the window of restaurant 2 and 1. Therefore he loses and points on the way to restaurant 3. There he eats a burger and gains another points. In total his happiness is equal to
8 and this is optimal.
Second testcase: His trip starts on day 1 at restaurant 1. Then his actions on day 2, 3 and 4 will be go to restaurant 2, stay at restaurant 2 and go to restaurant 4 respectively. The happiness of this optimal trip is equal to
15.
Third testcase: It's not worth to start the trip from any of the restaurant since he will only have negative happiness. That's why he should stay at home and
0 should be printed.
------------------------------------------------------------------------------------------------
Burger Happiness - Hacker Rank Solution
There exists a simple DP recurrence for which we can obtain an solution first. We will optimize this later with a data structure, but let's begin with the slower ones first. Many good solutions in CP always start from slow and simple ideas and get optimized with clever thinking.
Since every restaurant has one unique coordinate, we can redefine our denotation and say that the values and are for the restaurant located at .
We will introduce which means: is the maximum happiness we can get by ending our tour at restaurant located at .
The recurrence can be derived as where is the location of the previous restaurant that is also opened. Our solution will be then the maximum over all . is the happiness we lose on the path from to , which is also equal to the sum of 's of the opened restaurants when we move along from to .
OK, that's an algorithm.
As we might know, the sum of B's in an interval can be calculated with a very well known method. Since the sum between is equal to the sum between subtracted by the sum between we can somehow maintain the prefix sums dynamically with a Fenwick Tree or a Segment Tree.
Let's denote for all opened restaurants .
Consider the case in our DP recurrence again, but now with more handy definitions:
The value we need to maximize is only the term in the function. This actually means, we need to find in the interval an element with the maximum value.
Now do the case as an exercise, to find out which value we need to maximize for searching in the interval .
OK, this slowly starts to sound like a task involving RMQ (range maximum query) with segment tree, since we need to do range queries all the time to find the optimal values. Actually, if you figure out both cases, you will realize that we need to maintain two segment trees, since the values to maximize for both cases aren't the same.
Every time when we calculate our , we will add the corresponding values to our two segment trees at position so that future values can use this as an option for maximizing their values.
But wait, can be changing througout the time! No problem, if a burger restaurant opens at , it will affect all values that have coordinates greater than . Concretely, all elements in the interval will add to their value. This range updating can be done by using lazy propagation.
In total we will need two queries for each value to calculate. In total we will have time complexity of.
Hint: Coordinate compression on actually simplifies the implementation. :-)
Problem Setter's code :
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5;
const ll INF = 1LL << 62;
const int MAX_A = 1e6;
const int MAX_X = 1e9;
const int MAX_B = 1e6;
int N;
int X[MAX_N], A[MAX_N], B[MAX_N]; // Location, Gain, Lose
ll F[MAX_N];
int tmp[MAX_N];
struct SegmentTree {
ll lazy[MAX_N * 4];
ll T[MAX_N * 4];
void init(){
memset(lazy, 0, sizeof lazy);
memset(T, 0, sizeof T);
}
void propagate(int n, int L, int R){
T[n] += lazy[n];
if(L != R){
lazy[n * 2] += lazy[n];
lazy[n * 2 + 1] += lazy[n];
}
lazy[n] = 0;
}
void update(int n, int L, int R, int i, int j, ll x){
propagate(n, L, R);
if(R < i || j < L) return;
if(i <= L && R <= j){
lazy[n] = x;
propagate(n, L, R);
} else {
update(n * 2, L, (L + R) / 2, i, j, x);
update(n * 2 + 1, (L + R) / 2 + 1, R, i, j, x);
T[n] = max(T[n * 2], T[n * 2 + 1]);
}
}
void update(int i, int j, ll x){
if(i <= j)
update(1, 0, N - 1, i, j, x);
}
ll query(int n, int L, int R, int i, int j){
if(R < i || j < L) return -INF;
propagate(n, L, R);
if(i <= L && R <= j) return T[n];
return max(query(n * 2, L, (L + R) / 2, i, j),
query(n * 2 + 1, (L + R) / 2 + 1, R, i, j));
}
ll query(int i, int j){
if(i > j) return -INF;
return query(1, 0, N - 1, i, j);
}
};
SegmentTree T1; // Stores maximum f(x') + S[x' - 1]
SegmentTree T2; // Stores maximum f(x') - S[x']
ll query(int x, int a){
ll S = -T2.query(x, x); // S[x], since F[x] = 0
ll S1 = T1.query(x, x); // S[x - 1], since F[x] = 0
// Case x' < x
ll res1 = -S + a + T1.query(0, x - 1);
// Case x < x'
ll res2 = S1 + a + T2.query(x + 1, N - 1);
// Case Beginning from x
ll res3 = a;
return max(max(res1, res2), res3);
}
void update(int x, int b){
T1.update(x, x, F[x]);
T1.update(x + 1, N - 1, +b);
T2.update(x, x, F[x]);
T2.update(x, N - 1, -b);
}
int main(){
T1.init(), T2.init();
scanf("%d", &N);
assert(1 <= N && N <= MAX_N);
for(int i = 0; i < N; i++){
scanf("%d%d%d", X + i, A + i, B + i);
assert(0 <= X[i] && X[i] <= MAX_X);
assert(0 <= B[i] <= MAX_B);
assert(-MAX_A <= A[i] && A[i] <= MAX_A);
tmp[i] = X[i];
}
sort(tmp, tmp + N);
int m = unique(tmp, tmp + N) - tmp;
for(int i = 0; i < N; i++){
X[i] = lower_bound(tmp, tmp + m, X[i]) - tmp;
}
ll res = 0;
for(int i = 0; i < N; i++){
F[X[i]] = query(X[i], A[i]);
update(X[i], B[i]);
res = max(res, F[X[i]]);
}
printf("%lld\n", res);
return 0;
}
No comments:
Post a Comment