Submission #1103042

#TimeUsernameProblemLanguageResultExecution timeMemory
1103042rastervcFeast (NOI19_feast)C++17
100 / 100
140 ms14084 KiB
#include <iostream> constexpr long long INF = 1e18; constexpr int MAX_N = 3e5 + 5; int N, K, a[MAX_N]; std::pair<long long, int> dp[MAX_N][2]; std::pair<long long, int> check(long long lambda) { dp[1][0] = { 0, 0 }; dp[1][1] = { a[1] - lambda, 1 }; for (int i = 2; i <= N; ++i) { dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1]); dp[i][1] = std::max( std::make_pair(dp[i - 1][0].first + a[i] - lambda, dp[i - 1][0].second + 1), std::make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second) ); } return std::max(dp[N][0], dp[N][1]); } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> N >> K; for (int i = 1; i <= N; ++i) std::cin >> a[i]; long long l = 0, r = INF, ans = 0; while (l < r) { long long mid = (l + r + 1) >> 1; if (check(mid).second >= K) l = mid; else r = mid - 1; } std::cout << check(l).first + l * K; return 0; }

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:31:31: warning: unused variable 'ans' [-Wunused-variable]
   31 |     long long l = 0, r = INF, ans = 0;
      |                               ^~~
#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...