79122024-01-11 22:20:02adamBenzinkút üzemeltetés (55)cpp17Hibás válasz 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);


}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/55
1Hibás válasz0/03ms1812 KiB
2Hibás válasz0/027ms17652 KiB
3Hibás válasz0/33ms2232 KiB
4Hibás válasz0/33ms2604 KiB
5Hibás válasz0/33ms2768 KiB
6Hibás válasz0/33ms2780 KiB
7Hibás válasz0/32ms2884 KiB
8Hibás válasz0/33ms3024 KiB
9Hibás válasz0/33ms3424 KiB
10Hibás válasz0/33ms3616 KiB
11Hibás válasz0/33ms3784 KiB
12Hibás válasz0/38ms7672 KiB
13Hibás válasz0/412ms9472 KiB
14Hibás válasz0/414ms11512 KiB
15Hibás válasz0/518ms14020 KiB
16Hibás válasz0/620ms16592 KiB
17Hibás válasz0/627ms19864 KiB