Cod sursa(job #2631979)
Utilizator | Iliescu Andrei-Tudor Tudor_I | Data | 1 iulie 2020 19:01:15 |
---|---|---|---|
Problema | Transport | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.63 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("transport.in");
ofstream g("transport.out");
int n,k,c,a[16010],maxi,rez;
bool cond(int x)
{ int nr=0,s=0;
for(int i=1;i<=n&&nr<=k;i++)
{ if(s+a[i]>x) s=0,nr++;
s+=a[i];
}
if(s>0) nr++;
if(nr>k) return 0;
else return 1;
}
int main()
{
f>>n>>k;
for(int i=1;i<=n;i++)
{ f>>a[i];
if(a[i]>maxi) maxi=a[i];
}
int st,m,dr;
st=maxi;
dr=16000*n;
while(st<=dr)
{ m=(st+dr)/2;
if(cond(m)) dr=m-1,rez=m;
else st=m+1;
}
g<<rez;
return 0;
}