Cod sursa(job #2776269)
Utilizator | Ilinca Popescu ilincap2008 | Data | 19 septembrie 2021 10:04:23 |
---|---|---|---|
Problema | Transport | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.83 kb |
#include <fstream>
using namespace std;
ifstream cin ("transport.in");
ofstream cout ("transport.out");
int stiva[16001];
int n,k,i,mx,st,dr,mij,val,c,s;
int main()
{
cin >>n>>k;
for (i=1; i<=n; i++)
{
cin >>stiva[i];
if (stiva[i]>mx) {mx=stiva[i];}
}
st=mx;
dr=n*16000;
while (st<=dr)
{
mij=(st+dr)/2;
c=1;
s=0;
for (i=1; i<=n&&c<=k; i++)
{
if (s+stiva[i]>mij)
{
s=stiva[i];
c++;
}
else
{
s=s+stiva[i];
}
}
if (c<=k)
{
val=mij;
dr=mij-1;
}
else
{
st=mij+1;
}
}
cout <<val;
return 0;
}