Untitled
user_2087184
plain_text
a year ago
960 B
7
Indexable
#include <iostream> using namespace std; int a[100001], n, k; void solve(int index) { cin >> k >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } int sum = 0, max = 0, top = 0, pv = 0, maxSum = 0, result = 0; for (int i = 0; i < n; i++) { sum += a[i]; if (a[i] > max) max = a[i]; } if (k > 1) { top = (sum + max) / 2; maxSum = sum; while (pv <= k) { top = (maxSum + max) / 2; pv = 0; sum = 0; maxSum = 0; for (int i = 0; i < n; i++) { sum += a[i]; if (sum > top) { sum -= a[i]; pv++; if (sum > maxSum) maxSum = sum; sum = 0; sum += a[i]; } } pv++; if (pv <= k) { if (sum > maxSum) maxSum = sum; if (result == maxSum) { break; } result = maxSum; } } cout << result << endl; } else { cout << sum << endl; } } int main() { int t; cin >> t; for (int i = 1; i <= t; i++) { solve(i); } }
Editor is loading...
Leave a Comment