Problema "menu giapponese"

Aiuto
1

Com’è possibile che il correttore dia sbagliato il terzo caso di esempio (task 002, e sbaglia anche un altro caso che però non rientra tra gli esempi) quando sul mio PC dà il risultato giusto? O.o

Questo è il mio codice :

#include 
#include 
#include 

#define MAXN 5000

int N, b, ans=0;
std::vector sol, prezzi;


void ric(int i, int remW, std::vector p)
{
    if (ans == b) return;
    std::vector a=p;
    if(b-remW>ans && remW >= 0)
    {
        sol=a;
        ans=b-remW;
    }
    if(i==N || remW<0 || remW<prezzi[i]) return;
    ric(i+1, remW, a);          //take
    a.push_back(prezzi[i]);
    ric(i+1, remW-prezzi[i], a);//do not take
}

int main()
{
    int temp;
    std::vector p;
    scanf("%d %d", &N, &b);
    for(int i=0;i<N;i++)
    {
        scanf("%d", &temp);
        prezzi.push_back(temp);
    }
    ric(0, b, p);
    for(int i : sol)
        printf("%d\n", i);
    return 0;
}

E compilo con 

 g++ mat_menu.cpp -o mat_menu -std=c++11
2

Sono abbastanza sicuro che il testcase002 non coincida con il terzo esempio :sweat_smile:
(l’esercizio non è valutato a subtask e in questo caso 4 esempi coinciderebbero a 20 punti, che non sono pochi!)

Quindi il problema deve essere da qualche parte nel codice :confused:

3

Esatto, solo gli input 0 e 1 sono presi dagli esempi :smile:

Comunque questo è un classico caso in cui può essere un’ottima cosa fare un controllo incrociato con una soluzione lenta (magari esponenziale) provando tanti casi con pochi piatti (diciamo n = 5).