286 | 2021. 07. 04 22:22:47 | Valaki2 | Befektetés | cpp14 | Hibás válasz 6/40 | 48ms | 3012 KiB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4000;
const int maxk = 12000;
int n, k;
int dp[2][maxk+1];
int max_ado[2][maxk+1];
int ar[maxn+1];
int ertek[maxn+1];
int ado[maxn+1];
void solve() {
cin >> n >> k;
for(int i = 1; i <= n; ++i) cin >> ar[i] >> ertek[i] >> ado[i];
dp[1][ar[1]] = ertek[1];
max_ado[1][ar[1]] = ado[1];
for(int i = 1; i < n; ++i) {
for(int j = 0; j <= k; ++j) {
if(dp[(i + 1) % 2][j] < dp[i % 2][j]) {
dp[(i + 1) % 2][j] = dp[i % 2][j];
max_ado[(i + 1) % 2][j] = max_ado[i % 2][j];
}
if(dp[(i + 1) % 2][j - max_ado[i % 2][j] + max(max_ado[i % 2][j], ado[i + 1]) + ar[i + 1]] < dp[i % 2][j] + ertek[i + 1]) {
dp[(i + 1) % 2][j - max_ado[i % 2][j] + max(max_ado[i % 2][j], ado[i + 1]) + ar[i + 1]] = dp[i % 2][j] + ertek[i + 1];
max_ado[(i + 1) % 2][j - max_ado[i % 2][j] + max(max_ado[i % 2][j], ado[i + 1]) + ar[i + 1]] = max(max_ado[i % 2][j], ado[i + 1]);
}
}
}
int maxi = 0;
for(int i = 0; i <= k; ++i) maxi = max(maxi, dp[n % 2][i]);
cout << maxi << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 6/40 | ||||||
1 | Elfogadva | 0/0 | 2ms | 1852 KiB | |||
2 | Hibás válasz | 0/0 | 4ms | 2088 KiB | |||
3 | Elfogadva | 2/2 | 1ms | 1972 KiB | |||
4 | Hibás válasz | 0/2 | 1ms | 1984 KiB | |||
5 | Hibás válasz | 0/1 | 1ms | 1984 KiB | |||
6 | Elfogadva | 2/2 | 1ms | 2048 KiB | |||
7 | Hibás válasz | 0/2 | 1ms | 2048 KiB | |||
8 | Hibás válasz | 0/2 | 1ms | 2052 KiB | |||
9 | Elfogadva | 2/2 | 1ms | 2060 KiB | |||
10 | Hibás válasz | 0/2 | 1ms | 2068 KiB | |||
11 | Hibás válasz | 0/3 | 13ms | 2288 KiB | |||
12 | Hibás válasz | 0/3 | 12ms | 2336 KiB | |||
13 | Hibás válasz | 0/3 | 13ms | 2352 KiB | |||
14 | Hibás válasz | 0/3 | 12ms | 2396 KiB | |||
15 | Hibás válasz | 0/3 | 12ms | 2428 KiB | |||
16 | Hibás válasz | 0/4 | 12ms | 2452 KiB | |||
17 | Hibás válasz | 0/1 | 43ms | 2708 KiB | |||
18 | Hibás válasz | 0/1 | 41ms | 2764 KiB | |||
19 | Hibás válasz | 0/1 | 48ms | 2816 KiB | |||
20 | Hibás válasz | 0/1 | 43ms | 2940 KiB | |||
21 | Hibás válasz | 0/1 | 46ms | 2988 KiB | |||
22 | Hibás válasz | 0/1 | 43ms | 3012 KiB |