Cod sursa(job #2340333)
Utilizator | Treista Georgiana georgit | Data | 10 februarie 2019 11:57:07 |
---|---|---|---|
Problema | Transport | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.67 kb |
#include <fstream>
#define N 16000
using namespace std;
int a[N+5],n,k;
bool ok(int x)
{
int s=0,nr=1;
for(int i=1;i<=n;i++)
{
if(a[i]>x)
return 0;
if(s+a[i]<=x)
s+=a[i];
else
{
nr++;
s=a[i];
}
}
return (nr<=k);
}
int main()
{
ifstream f("transport.in");
ofstream g("transport.out");
f>>n>>k;
for(int i=1;i<=n;i++)
f>>a[i];
int st=1,dr=(1<<30)+1;
while(dr-st>1)
{
int mij=(st+dr)/2;
if(ok(mij))
dr=mij;
else
st=mij;
}
g<<dr;
return 0;
}