Cod sursa(job #2638944)
Utilizator | vladdd vladdobro07 | Data | 30 iulie 2020 17:39:49 |
---|---|---|---|
Problema | Transport | Scor | 80 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.85 kb |
#include <fstream>
using namespace std;
ifstream cin("transport.in");
ofstream cout("transport.out");
int v[16001];
bool verif(int x,int n,int k) {
int sk=0,c=1;
for(int i=1; i<=n; i++) {
if(v[i]+sk<=x)
sk+=v[i];
else {
sk=v[i];
c++;
}
}
return (c>k);
}
int main() {
int n,k,minn,maxx,x,s=0,mid,sk=0,last,ans=0;
int p_max=28;
cin>>n>>k;
for(int i=1; i<=n; i++) {
cin>>x;
v[i]=x;
s+=x;
}
maxx=s;
minn=s/k;
for(int i = (1 << p_max); i > 0; i /= 2) {
if(verif(ans + i,n,k))
ans += i;
}
cout<<ans+1;
return 0;
}