Cerinta completa

You have two arrays of integers, and , where both have number of elements. Consider the following function:

score = 0

int Go(step, energy) {
    if (step == N) {
        score += V[step];
        return (score);
    }
    else {
        int way = random(1, 2);
        if (way == 1) {
            score += V[step];
        }
        else {
            energy = P[step];
        }
        if (energy > 0) {
            Go(step + 1, energy - 1);
        }
        else {
            KillTheWorld();
        }
    }
}

What is the maximum possible value of score that we can get in the end, if we call ?.
Note that the function should never invoke KillTheWorld function. And generates a random integer from set [1, 2].
It is guaranteed there will be a solution that wont kill the world.

Input Format

The first line contains an integer N. Each of the following N lines contains a pair of integers. The i-th line contains a pair of numbers, , separated by space.

Constraints



Output Format

Derive the maximum score given by return (score);.

Sample Input

4
4 2
0 2
4 0
3 4

Sample Output

7

Explanation

In the best case, the first and second function call in Go variable will take value 2, while in the other calls it will be equal to 1 then the final score will be equal to the value of 7.

Limbajul de programare folosit: cpp20

Cod:

#include <bits/stdc++.h>
using namespace std;

long long robot(const vector<vector<int>>& vp) {
    int n = (int)vp.size();
    vector<long long> v(n + 1, 0);
    vector<int> p(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        v[i] = vp[i - 1][0];
        p[i] = vp[i - 1][1];
    }

    if (n == 0) return 0;
    if (n == 1) return v[1];

    long long total = 0;
    for (int i = 1; i <= n; ++i) total += v[i];

    const long long INF = (1LL << 62);
    vector<long long> dp(n + 1, INF);

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    dp[1] = v[1];
    int end1 = min(n - 1, 1 + p[1]);
    if (end1 >= 2) pq.push({dp[1], end1});

    for (int j = 2; j <= n - 1; ++j) {
        while (!pq.empty() && pq.top().second < j) pq.pop();
        if (pq.empty()) continue;

        dp[j] = pq.top().first + v[j];

        int endj = min(n - 1, j + p[j]);
        if (endj >= j + 1) pq.push({dp[j], endj});
    }

    long long minResetCost = INF;
    for (int i = 1; i <= n - 1; ++i) {
        if (dp[i] == INF) continue;
        if ((long long)i + p[i] >= n) {
            minResetCost = min(minResetCost, dp[i]);
        }
    }

    return total - minResetCost;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<vector<int>> vp(n, vector<int>(2));
    for (int i = 0; i < n; ++i) {
        cin >> vp[i][0] >> vp[i][1];
    }

    cout << robot(vp) << endl;
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464632414

Link challenge: https://www.hackerrank.com/challenges/robot/problem

Robot