Pagini recente » Cod sursa (job #1693646) | Clasament allyoucancode2008 | Cod sursa (job #1522253) | Cod sursa (job #781012) | Cod sursa (job #1435044)
#include <fstream>
using namespace std;
ifstream fin("transport.in");
ofstream fout("transport.out");
int v[160001], n, k, cnt;
long long low, high, mid, curr;
int main() {
fin >> n >> k;
for (int i = 1; i <= n; i++) {
fin >> v[i];
high += v[i];
if (v[i] > low)
low = v[i];
}
while (low <= high) {
mid = (high - low) / 2 + low;
cnt = 1;
curr = 0;
for (int i = 1; i <= n; i++)
if (v[i] + curr > mid) {
cnt++;
curr = v[i];
} else curr += v[i];
if (cnt > k)
low = mid + 1;
else high = mid - 1;
}
fout << low;
return 0;
}