Cod sursa(job #3160782)
Utilizator | Matei Lupu mateilupu | Data | 25 octombrie 2023 08:38:14 |
---|---|---|---|
Problema | Transport | Scor | 0 |
Compilator | cpp-32 | Status | done |
Runda | Arhiva de probleme | Marime | 0.69 kb |
#include <iostream>
using namespace std;
int main()
{
int v[16001], n, k, i, st = -1, dr = 0, m, s, cnt, sol;
cin >> n >> k;
for(i = 1; i <= n; i++) {
cin >> v[i];
dr += v[i];
if(v[i] > st)
st = v[i];
}
while(st <= dr) {
m = (st + dr) / 2;
cnt = 1;
s = 0;
for(i = 1; i <= n; i++) {
if(s + v[i] <= m)
s += v[i];
else {
s = v[i];
cnt++;
}
}
if(cnt > k)
st = m + 1;
else {
sol = m;
dr = m - 1;
}
}
cout << sol;
return 0;
}