Cod sursa(job #1326580)
Utilizator | Data | 25 ianuarie 2015 17:51:45 | |
---|---|---|---|
Problema | Transport | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.88 kb |
#include <fstream>
using namespace std;
ifstream fin("transport.in");
ofstream fout("transport.out");
int v[16014];
int i,mij,k,n,st,dr,tr,s,mini;
int main()
{
fin>>n>>k;
s=0;
for(i=1;i<=n;i++)
{
fin>>v[i];
s=s+v[i];
}
st=1;
dr=s;
while(st<=dr)
{
s=0;
tr=0;
mij=st+(dr-st)/2;
for(i=1;i<=n;i++)
{
s=s+v[i];
if(v[i]>mij)
{
tr=k+1;
break;
}
if(s+v[i+1]>mij)
{
tr++;
s=0;
}
}
tr++;
if(tr<=k)
{
mini=mij;
dr=mij-1;
}
else
st=mij+1;
}
fout<<mini;
return 0;
}