Cod sursa(job #3184922)
Utilizator | Saila Darius Derius | Data | 17 decembrie 2023 13:17:51 |
---|---|---|---|
Problema | Transport | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.78 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("transport.in");
ofstream fout("transport.out");
int v[16001];
int main()
{
int n,i,k,medie=0,maxi=-1,st,dr,sum=0,mij,s,nrt;
fin>>n>>k;
for(i=1;i<=n;i++)
{
fin>>v[i];
sum+=v[i];
if(v[i]>maxi)
maxi=v[i];
}
medie=sum/k;
if(maxi<medie)
maxi=medie;
st=maxi;
dr=sum;
while(st<dr)
{
mij=(st+dr)/2;
s=0;
nrt=1;
for(i=1;i<=n;i++)
{
s+=v[i];
if(s>mij)
{
s=v[i];
nrt++;
}
}
if(nrt>k)
st=mij+1;
if(nrt<=k)
dr=mij;
}
fout<<st;
return 0;
}