# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1097172 | crafticat | Feast (NOI19_feast) | C++17 | 241 ms | 262144 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
template<typename T>
using V = vector<T>;
using ll = long long;
#define ckmax(a,b) a= max(a,b)
ll solve(V<ll>&arr, ll k, ll p) {
V<V<V<ll>>> dp(arr.size() + 1, V<V<ll>>(k + 1, V<ll>(2, -1e18)));
dp[0][0][1] = 0;
for (ll i = 1; i <= arr.size(); ++i) {
dp[i][0][1] = 0;
for (ll j = 1; j <= k; ++j) {
for (ll l = 0; l < 2; ++l) {
dp[i][j][l] = max(dp[i - 1][j - 1][1], dp[i - 1][j][1]);
if (l == 0) ckmax(dp[i][j][l], dp[i - 1][j][0]);
ckmax(dp[i][j][l], dp[i - 1][j - 1][0]);
if (l == 1) dp[i][j][l] += arr[i - 1];
}
}
}
return max(dp[arr.size()][k][0], dp[arr.size()][k][1]);
}
int main() {
ll n, k; cin >> n >> k;
V<ll> arr(n);
for (ll i = 0; i < n; ++i) {
cin >> arr[i];
}
cout << solve(arr,k,1);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |