Maximizing Mission Points – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Cerinta completa

Xander Cage has a list of cities he can visit on his new top-secret mission. He represents each city as a tuple of . The values of , , and are distinct across all cities.

We define a mission as a sequence of cities, , that he visits. We define the total of such a mission to be the sum of the of all the cities in his mission list.

Being eccentric, he abides by the following rules on any mission:

He can choose the number of cities he will visit (if any).
He can start the mission from any city.
He visits cities in order of strictly increasing .
The absolute difference in between adjacent visited cities in his mission must be at most .
The absolute difference in between adjacent visited cities in his mission must be at most .

Given , , and the definitions for cities, find and print the maximum possible total that Xander can earn on a mission.

Input Format

The first line contains three space-separated integers describing the respective values of , , and .
Each line of the subsequent lines contains four space-separated integers denoting the respective , , , and for a city.

Constraints

Output Format

Print a single integer denoting the maximum possible that Xander can earn on a mission.

Sample Input 0

Sample Output 0

Explanation 0

Xander can start at city , then go to city , and then go to city for a maximum value of total

Note that he cannot go directly from city to city as that would violate his rules that the absolute difference in between adjacent visited cities be and the absolute difference in between adjacent visited cities be . Because and , he cannot directly travel between those cities.

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const long long INF = 1e15;

long long tree[MAXN * 4];

void makeTree() {
    for (int i = 1; i < MAXN * 4; ++i) {
        tree[i] = -INF;
    }
}
void update(int x, long long val, int u = 1, int l = 1, int r = MAXN) {
    if (l == r) {
        tree[u] = val;
        return;
    }
    int m = (l + r) / 2;
    if (x <= m) {
        update(x, val, 2 * u, l, m);
    }
    else {
        update(x, val, 2 * u + 1, m + 1, r);
    }
    tree[u] = max(tree[2 * u], tree[2 * u + 1]);
}

long long query(int x, int y, int u = 1, int l = 1, int r = MAXN) {
    if (x > r or y < l) {
        return -INF;
    }
    if (x <= l and r <= y) {
        return tree[u];
    }
    int m = (l + r) / 2;
    return max(query(x, y, 2 * u, l, m), query(x, y, 2 * u + 1, m + 1, r));
}

struct Point {
    int x, y, z, w;
    long long dp;
    bool operator < (const Point &o) const {
        return z < o.z;
    }
};
Point p[MAXN + 1];
long long DP[MAXN + 1];
int X_LIM, Y_LIM;
void merge(int l, int r) {
    int m = (l + r) / 2;

    vector<pair<int, int> > left;
    vector<pair<int, int> > right;
    for (int i = l; i <= m; ++i) {
        left.push_back({p[i].x, p[i].z});
    }       
    for (int i = m + 1; i <= r; ++i) {
        right.push_back({p[i].x, p[i].z});
    }
    sort(left.begin(), left.end());
    sort(right.begin(), right.end());

    int left_l = 0;
    int left_r = -1;
    for (auto u : right) {
        int i = u.second;
        int x = u.first;
        while (left_r + 1 < left.size() and left[left_r + 1].first - x <= X_LIM) {
            ++left_r;
            int who = left[left_r].second;
            update(p[who].y, p[who].dp);            
        }
        while (left_l < left.size() and x - left[left_l].first > X_LIM) {
            int who = left[left_l].second;
            update(p[who].y, -INF);
            ++left_l;
        }
        int yLow = max(1, p[i].y - Y_LIM);
        int yHigh = min(MAXN, p[i].y + Y_LIM);
        p[i].dp = max(p[i].dp, p[i].w + query(yLow, yHigh));
    } 
    while (left_l <= left_r) {
        int who = left[left_l].second;
        update(p[who].y, -INF);
        ++left_l;
    }
}
void solve(int l, int r) {
    if (l == r) {
        p[l].dp = max(p[l].dp, (long long)p[l].w);
        return;
    }
    int m = (l + r) / 2;
    solve(l, m);
    merge(l, r);
    solve(m + 1, r);
}
int main() {
    makeTree();
    int n;
    scanf("%d %d %d", &n, &X_LIM, &Y_LIM); 
    for (int i = 0; i < n; ++i) {
        scanf("%d %d %d %d", &p[i].x, &p[i].y, &p[i].z, &p[i].w);
        p[i].dp = -INF;
    }
    sort(p, p + n);
    for (int i = 0; i < n; ++i) {
        p[i].z = i;
    }
    solve(0, n - 1);
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, p[i].dp);
    }
    printf("%lld\n", ans);
}

Scor obtinut: 1.0

Submission ID: 464646991

Link challenge: https://www.hackerrank.com/challenges/maximizing-mission-points/problem

Maximizing Mission Points