79122024-01-11 22:20:02adamBenzinkút üzemeltetés (55)cpp17Wrong answer 0/5527ms19864 KiB
#include <bits/stdc++.h>
using namespace std;

vector<int> dist, profit;
int stop_count, min_dist;

vector<vector<pair<int, int>>> memo;

int solve(int n, int before) {
    if(n == stop_count+1) return 0;
    else if (memo[n][before] != pair(-1, -1)) return memo[n][before].first;
    int answer = 0;

    int b = solve(n + 1, before);

    if (dist[n] - dist[before] >= min_dist) {
        answer = profit[n] + solve(n+1, n);
    }
    if (answer > b) {
        memo[n][before] = {answer, 0};
    } else {
        memo[n][before] = {b, 1};
    }
    return memo[n][before].first;
}



int main() {

    cin >> stop_count >> min_dist;
    dist.assign(stop_count +1, 0);
    profit.assign(stop_count +1, 0);
    dist[0] = 0 - min_dist - 1;
    profit[0] = 0 - min_dist - 1;
    memo.assign(stop_count + 1, vector<pair<int, int>>(stop_count+1, {-1, -1}));


    for (int i = 1; i <= stop_count; i++) {
        cin >> dist[i] >> profit[i];
    }

    cout << solve(1, 0);


}
SubtaskSumTestVerdictTimeMemory
base0/55
1Wrong answer0/03ms1812 KiB
2Wrong answer0/027ms17652 KiB
3Wrong answer0/33ms2232 KiB
4Wrong answer0/33ms2604 KiB
5Wrong answer0/33ms2768 KiB
6Wrong answer0/33ms2780 KiB
7Wrong answer0/32ms2884 KiB
8Wrong answer0/33ms3024 KiB
9Wrong answer0/33ms3424 KiB
10Wrong answer0/33ms3616 KiB
11Wrong answer0/33ms3784 KiB
12Wrong answer0/38ms7672 KiB
13Wrong answer0/412ms9472 KiB
14Wrong answer0/414ms11512 KiB
15Wrong answer0/518ms14020 KiB
16Wrong answer0/620ms16592 KiB
17Wrong answer0/627ms19864 KiB