el problema "supermercado" del qr de coderoads coding contest (tarda unos 5 minutos en generar las respuestas del caso difícil D:)

supermercado

//#define NDEBUG

#include <cstring>
#include <string>
#include <queue>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <fstream>
#include <assert.h>
#include <set>
#include <map>
#include <cstdio>

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<char> vc;
typedef pair<int,int> ii;
typedef pair<string,string> ss;

int m;
vector<set<int> > dp(1000, set<int>());

int bottomup(vi P, int b) {
  set<int> M;
  M.insert(b);
  if(b-P[0] > 0)
    M.insert(b-P[0]);
  else if(b-P[0] == 0) 
    return b;
  
  for(int i=1; i<P.size(); i++) {
    for(int element: M) {
      if(element-P[i] > 0) 
	M.insert(element-P[i]);
      else if(element-P[i] == 0)
	return b;
    }

    if(b-P[i] > 0) 
      M.insert(b-P[i]);
    else if(b-P[i] == 0)
      return b;
  }
  return b-*M.begin();
  
}

int topdown(vi P, int b) {
  vector<set<int> > M(P.size()+1, set<int>());
  
  M[0].insert(b);
  if(b-P[0] >= 0)
    M[0].insert(b-P[0]);
  
  for(int i=1; i<M.size(); i++) {
    for(int element: M[i-1]) {
      M[i].insert(element);

      if(element-P[i] >= 0) {
	M[i].insert(element-P[i]);
      }
    }

    if(b-P[i] >= 0)
      M[i].insert(b-P[i]);
  }

  return b- *M[P.size()].begin();
}

void knapsack(int i, int res, vi P) {
  if(i == P.size() || res < 0) {
    if(res >= 0) {
      dp[i].insert(res);
      m = min(m, res);
    }
    return;
  }

  m = min(m, res);

  if(i>0)
    for(int element : dp[i-1]) 
      dp[i].insert(element);
  
  if((res-P[i]) >= 0 && dp[i].count(res-P[i]) == 0) {
    dp[i].insert(res-P[i]);
    knapsack(i+1, res-P[i], P);    
  } 
  
  if(dp[i].count(res) == 0) {
    dp[i].insert(res);
    knapsack(i+1, res, P);    
  }

}

int main(){
  int t;
  scanf("%d", &t);
  
  while(t--) {
    dp.assign(1000, set<int>());
    int b, p;
    scanf("%d %d", &b, &p);
    m = b;
    vi P(p);

    for(int i=0; i<p; i++) {
      scanf("%d", &P[i]);
    }
    
    cout << bottomup(P, b) << endl;
  }
  return 0;
}