Submission #1103043

#TimeUsernameProblemLanguageResultExecution timeMemory
1103043rastervcFeast (NOI19_feast)C++17
18 / 100
88 ms11036 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]); } int32_t 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; std::pair<long long, int> res = check(mid); if (res.second >= K) { ans = res.first + mid * K; l = mid + 1; } else r = mid - 1; } std::cout << ans; return 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...