Cod sursa(job #462004)
#include<stdio.h>
using namespace std;
int v[100017];
int K, n;
int rez, i;
long int S, st, dr, mijl;
int calcul (int x)
{
int aux = x;
int nr = 0, i = 1;
while (nr < K && i <= n)
{
if(v[i] > x)
{
nr ++;
i ++;
continue;
}
aux -= v[i];
if (aux < 1)
{
aux += x;
nr ++;
}
i ++;
}
if (nr < K)
return 0;
return 1;
}
int main ()
{
FILE *f = fopen ("grupuri.in","r");
FILE *g = fopen ("grupuri.out","w");
fscanf (f,"%d %d", &K, &n);
for(i=1; i<=n; ++i)
{
fscanf (f,"%d", &v[i]);
S += v[i];
}
st = 1;
dr = S / K;
while (st <= dr)
{
mijl = (st + dr) / 2;
rez = calcul (mijl);
if (!rez)
dr = mijl - 1;
else
st = mijl + 1;
}
fprintf(g, "%ld\n", dr);
fclose(g);
fclose(f);
return 0;
}