Submission #439908

#TimeUsernameProblemLanguageResultExecution timeMemory
439908dongliu0426Feast (NOI19_feast)C++14
39 / 100
217 ms13908 KiB
#include <bits/stdc++.h> using namespace std; #define N 300000 #define INF 0x3f3f3f3f3f3f3f3f int n, k, a[N + 1]; pair<long long, int> dp[N + 1][2]; template<class T, class U> T lastTrue(T lo, T hi, U f) { assert(lo <= hi); --lo; /* assuming f is decreasing */ while (lo < hi) { /* find last index such that f is true */ T mid = lo + (hi - lo + 1) / 2; f(mid) ? lo = mid : hi = mid - 1; } return lo; } int main() { scanf("%d%d", &n, &k); long long sum = 0; for (int i = 1; i <= n; ++i) scanf("%d", a + i), sum += a[i]; auto check = [&](long long penalty) { dp[0][0] = {0, 0}, dp[0][1] = {-INF, 0}; for (int i = 1; i <= n; ++i) { pair<long long, int> last = max(dp[i - 1][0], dp[i - 1][1]); dp[i][0] = max(make_pair(last.first - penalty, last.second + 1), last); dp[i][1] = max(make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second), make_pair(dp[i - 1][0].first + a[i] - penalty, dp[i - 1][0].second + 1)); } return max(dp[n][0], dp[n][1]).second >= k; }; long long penalty = lastTrue<long long>(0, INF, check); check(penalty); printf("%lld\n", max(dp[n][0], dp[n][1]).first + penalty * k); }

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
feast.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d", a + i), sum += a[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...