Cod sursa(job #3166964)
Utilizator | Mogonea Mihnea Mihai MogoneaMIhnea | Data | 9 noiembrie 2023 20:37:00 |
---|---|---|---|
Problema | Transport | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.74 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("transport.in");
ofstream fout("transport.out");
int n, k, s,v[16001], i, st, dr, sum, aux, mini, mid;
void suma(int m){
for(i=1;i<=k;i++){
sum=0;
while(sum+v[aux]<=m && aux<=n){
sum+=v[aux];
aux++;
}
}
}
int main(){
fin>>n>>k;
for(i=1;i<=n;i++){
fin>>v[i];
s+=v[i];
}
st=1;
dr=s;
while(st<=dr){
mid=(st+dr)/2;
aux=1;
suma(mid);
if(aux>n){
dr=mid-1;
mini=mid;
}else
st=mid+1;
}
fout<<mini;
}
/*
6 3
7
3
2
3
1
4
s=20
mini=8;
*/