Cod sursa(job #3167282)
Utilizator | matei dia maftei | Data | 10 noiembrie 2023 15:39:40 |
---|---|---|---|
Problema | Transport | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.8 kb |
#include <fstream>
using namespace std;
ifstream cin("transport.in");
ofstream cout("transport.out");
int n,m,i,j,k,s,rez,st,dr,mid,last,sum,nr,maxim;
int v[16010];
int main () {
cin>>n>>k;
for (i=1;i<=n;i++) {
cin>>v[i];
s+=v[i];
if(maxim<v[i])
maxim=v[i];
}
st=maxim;
dr=s;
while (st<=dr) {
mid=(st+dr)/2;
sum=0;
nr=0;
for (i=1;i<=n;i++) {
sum+=v[i];
if (sum==mid) {
nr++;
sum=0;
}
if (sum>mid) {
nr++;
sum=0;
i--;
}
}
if (nr<k) {
dr=mid-1;
}
else {
st=mid+1;
}
}
cout<<st;
}