Cod sursa(job #1036029)
Utilizator | onici bianca Biancageorgiana | Data | 18 noiembrie 2013 22:23:36 |
---|---|---|---|
Problema | Transport | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.76 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("transport.in");
ofstream g("transport.out");
int main()
{
int v[16000],max=0,smax,s=0,i,n,st,dr,drum,k,m;
f>>n;
f>>k;
for(i=1;i<=n;i++)
{
f>>v[i];
if(v[i]>max)
max=v[i];
smax+=v[i];
}
st=max;
dr=smax;
while(st!=dr)
{
m=(st+dr)/2;
s=0;
drum=1;
for(i=1;i<=n;i++)
{
if(s+v[i]<=m)
s+=v[i];
else
{
s=v[i];
drum++;
}
}
if(drum>k)
st=m+1;
else
dr=m;
}
g<<m;
f.close();
g.close();
return 0;
}