Submission #1209989

#TimeUsernameProblemLanguageResultExecution timeMemory
1209989blazerFeast (NOI19_feast)C++20
0 / 100
36 ms2632 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int N, K; vector <int> A; pair<int, int> compute(int penalty) { int total = 0, segments = 0, curr = 0; for (int i = 0; i < N; ++i) { curr += A[i]; if (curr - penalty > 0) { total += curr - penalty; ++segments; curr = 0; } else if (curr < 0) { curr = 0; } } return {total, segments}; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> K; A.resize(N); for (int& x : A) cin >> x; int low = 0, high = 1e14, best = 0; while (low <= high) { int mid = (low + high) / 2; auto [gain, segs] = compute(mid); if (segs <= K) { best = gain + mid * segs; high = mid - 1; } else { low = mid + 1; } } cout << best; 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...