Submission #1097172

#TimeUsernameProblemLanguageResultExecution timeMemory
1097172crafticatFeast (NOI19_feast)C++17
59 / 100
241 ms262144 KiB
#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)

feast.cpp: In function 'll solve(V<long long int>&, ll, ll)':
feast.cpp:13:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (ll i = 1; i <= arr.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...