Cod sursa(job #2537019)
Utilizator | Berendea Andrei Berea | Data | 2 februarie 2020 22:02:53 |
---|---|---|---|
Problema | Transport | Scor | 50 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.8 kb |
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
int n,i,x,k,c,s,st,dr,med,poz;
vector<int>v;
int main()
{
ifstream fin("transport.in");
ofstream fout("transport.out");
fin>>n>>k;
for (i=0;i<n;i++)
{
fin>>x;
v.push_back(x);
s=s+x;
}
st=0;
dr=s*k;
c=k+1;
while (st<=dr)
{
med=(st+dr)/2;
x=0;
c=1;
for (i=0;i<v.size();i++)
{
x=x+v[i];
if (x>med)
{
x=v[i];
c++;
}
}
if (c>k)
{
st=med+1;
}
if (c<=k)
{
poz=med;
dr=med-1;
}
}
fout<<poz;
}