Programación Competitiva

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long int presupuesto, p;
    while(scanf("%lld %lld",&presupuesto,&p)==2){
        long long int presus[p];
        for(int i=0; i<p;i++) scanf("%lld",&presus[i]);
        sort(presus,presus+p);
        long long int res;
        long long int acum=0;
        if(p==0) res = 0;
        else res = presus[p-1];
        for(int i=0; i<p;i++){
            acum+=presus[i];
            long long int gastoTotal = acum + presus[i]*(p-i-1);
            if(gastoTotal==presupuesto) {
                res=presus[i];
                break;
            }
            if(gastoTotal>presupuesto){
                if(i==0) res = presupuesto/p;
                else {
                    long long int ultimos = presus[i-1]*(p-i);
                    long long int restante = presupuesto-acum+presus[i]-ultimos;
                    res = presus[i-1] + restante/(p-i);
                }
                break;
            }
        }
        printf("%lld\n",res);
    }
    return 0;
}

/*
0 5
1 2 3 4 5
1 5
1 2 3 4 5
2 5
1 2 3 4 5
3 5
1 2 3 4 5
4 5
1 2 3 4 5
5 5
1 2 3 4 5
6 5
1 2 3 4 5
7 5
1 2 3 4 5
8 5
1 2 3 4 5
9 5
1 2 3 4 5
10 5
1 2 3 4 5
11 5
1 2 3 4 5
12 5
1 2 3 4 5
13 5
1 2 3 4 5
14 5
1 2 3 4 5
15 5
1 2 3 4 5
16 5
1 2 3 4 5
10 1
20
10 2
20 20
10 0
10 1
10
20 6
6 3 9 6 9 6
20 6
2 9 8 2 8 3
20 6
7 8 9 4 7 8
20 6
3 8 10 2 7 4
20 6
4 7 1 6 10 3
20 6
4 9 7 10 8 2
20 6
6 4 6 2 5 7
20 6
9 9 3 10 4 3
20 6
1 8 3 10 10 5
20 6
1 10 6 2 8 10
20 6
8 8 6 10 7 10
20 6
4 5 8 10 6 2
20 6
3 9 6 10 5 5
20 6
3 5 10 9 7 10
20 6
10 7 7 10 9 4
20 6
5 3 2 2 1 10
20 6
9 6 8 1 5 8
20 6
3 10 8 4 9 1
20 6
9 1 1 3 10 10
20 6
1 10 9 6 3 8
20 6
1 10 1 9 9 6
20 6
2 8 7 4 7 7
20 6
4 2 5 8 3 5
20 6
5 5 3 7 5 2
20 6
1 3 8 1 6 10
20 6
1 1 8 8 10 6
20 6
6 2 5 3 7 7
20 6
2 6 7 3 6 1
20 6
5 3 4 8 10 8
20 6
1 7 9 7 5 1
20 6
5 7 5 8 8 9
20 6
7 9 6 3 5 10
20 6
1 1 6 10 5 4
20 6
2 6 3 8 2 4
20 6
6 7 9 6 1 4
20 6
1 9 1 6 6 3
20 6
6 7 1 9 1 2
20 6
4 4 3 2 5 5
20 6
6 7 10 3 7 3
20 6
8 10 9 4 2 7
100 20
10 1 2 7 8 1 10 7 6 4 2 6 8 6 6 5 2 5 4 5
100 20
10 1 10 9 8 8 5 8 5 10 10 3 5 10 8 1 7 3 9 7
100 20
1 8 10 9 3 1 8 1 4 8 9 9 9 8 5 4 9 5 2 2
100 20
9 7 1 5 3 10 7 8 8 6 1 8 2 3 2 4 8 7 5 9
100 20
5 1 1 3 9 8 8 8 1 1 1 10 1 10 4 8 7 2 5 5
100 20
5 9 9 10 9 2 7 8 10 7 4 2 2 9 4 9 9 3 8 4
100 20
1 3 5 1 1 2 5 7 1 5 5 2 5 10 8 8 9 8 3 6
100 20
4 6 5 3 1 3 6 8 5 3 7 4 1 2 9 2 1 6 2 6
100 20
6 1 7 2 9 3 8 7 1 1 9 8 9 6 6 10 9 7 5 4
100 20
1 9 5 4 2 5 3 10 5 9 5 3 4 10 2 10 7 8 8 8
100 20
4 2 10 7 1 4 5 2 2 1 9 2 6 5 6 2 4 7 4 5
100 20
9 2 4 3 3 6 5 1 1 10 1 6 2 10 5 5 8 1 1 2
100 20
4 4 4 6 1 10 9 5 9 5 8 5 9 8 8 6 3 3 7 3
100 20
6 8 4 5 4 7 1 9 8 6 6 8 9 9 3 8 1 3 6 6
100 20
2 2 4 9 2 9 6 7 10 7 8 8 8 6 1 8 8 1 1 1
100 20
10 3 2 5 10 5 7 10 8 5 4 5 5 6 4 6 7 2 5 5
100 20
9 9 3 1 2 10 2 6 6 9 9 3 5 3 7 5 6 3 7 6
100 20
10 1 9 4 9 7 10 4 2 3 10 1 1 10 2 5 9 1 3 2
100 20
1 7 4 6 3 7 1 4 10 9 5 3 1 4 9 1 6 5 9 3
100 20
8 8 1 7 2 4 4 10 7 9 4 7 4 10 7 2 4 6 5 1

CUIDADO CON LOS CASOS DE LONG LONG!!!

0
0
0
0
1
1
1
1
2
2
2
3
3
4
5
5
10
5
0
10
3
4
3
3
4
3
3
3
4
4
3
3
3
3
3
7
3
4
5
4
4
3
3
3
5
4
3
4
3
4
3
3
4
4
3
5
5
3
3
3
7
5
7
6
10
6
10
9
6
6
10
10
6
6
7
6
7
9
10
*/