schema

#include<fstream>
#include<bitset>
#include<algorithm>
using namespace std;
ifstream cin("schema.in");
ofstream cout("schema.out");
const int GMAX = 5e3 + 1;
const int NMAX = 2e3 + 1;
int cost[NMAX],suffix[NMAX];
bitset<GMAX> pot;
bitset<GMAX> nou;


int main()
{
    pot[0] = 1;
    int n,g;
    cin >> n >> g;
    for(int i = 1; i <= n ; i++)
        {
            cin >> cost[i];
        }
    sort(cost + 1,cost + 1 + n,greater<int> ());

    /// construiesc sufixe
    suffix[n] = 0;
    for(int i = n - 1; i >= 1; i--)
        {
            suffix[i] = suffix[i + 1] + cost[i + 1];
        }
    /// dinamica
    int maxbani = g - suffix[1] - cost[1]; /// cazul in care investesc in toate proiectele

    for(int nu = 1; nu <= n ; nu++) /// fixez cel mai mic proiect in care nu investesc
        {
            int mici = suffix[nu]; /// investesc automat in cele care au costul mai mic

            for(int mari = 0; mari <= g ; mari++) /// selectez o submultime de proiecte care au toate costul mai mare decat proiectul in care nu investesc
                {
                    if(pot[mari]) ///verific daca pot face suma cu o submultime de proiecte mai mari de pana acum
                        {
                            int rez = g - mici - mari; /// suma de bani ramasa dupa investitiile facute

                            if(rez >= 0 && rez < cost[nu]) // verific daca rezultatul e mai mic decat proiectul in care nu trebuie sa investim
                                {
                                    maxbani = max(maxbani,rez); ///updatez maximul
                                }
                        }
                }
            nou.reset();
            for(int mari = 0 ; mari <= g ; mari++) /// updatez dinamica
                {
                    if(pot[mari])
                        {
                        	nou[mari] = 1;
                            if((mari + cost[nu]) <= g)
                                {
                                    nou[mari + cost[nu]] = 1;
                                }
                        }
                }
                pot = nou;
        }
   cout<<maxbani<<'\n';
   cin.close();
   cout.close();
   return 0;
}