Correttore buggato?


#1

Ciao a tutti!
premetto che ho cercato errori simili, sono sempre stati risolti o è stata trovata una possibile spiegazione ma questo è proprio strano…

Stavo risolvendo “Pranzo dalla nonna”; avevo fatto 100 già l’anno scorso ma volevo sottoporre una soluzione più rapida per sfizio personale;
Ho scritto una soluzione sicuramente più rapida MA sebbene mi dia giusti tutti i casi complicati, sono considerati errati un paio di casi da input piccolino e… i casi d’esempio!

Ecco il codice

#include <bits/stdc++.h>

using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");

int minimo = 1000001;
//knapsack / problema delle monete - su array monodimensionale

int main()
{
	int N,K;
	fin>>N>>K;
	
	bool memo[K];
	memo[0] = true;
	
	vector<int> newValues;   //vettore con gli appigli per continuare a sommare
	newValues.push_back(0);
	
	for(int i=0;i<N;i++)
	{
		int piatto;
		fin>>piatto; 
		
		if(piatto >= K)
		{
			if(piatto < minimo)	
				minimo = piatto;
		}
		else   //piatto è minore di K, allora lo sommo a tutti gli n precedenti che si trovano in newValues
		{ 
			for(int j=newValues.size()-1;j>=0;j--) //posso anche registrare newValues.size() in una variabile e poi fare for(int j=0;j<DIMENSIONE;j++)
                                                   //così sono sicuro che non varia (causando un loop infinito)
			{
				if(piatto + newValues[j] < K)
				{
					if(memo[piatto + newValues[j]] != true)
					{
						memo[piatto + newValues[j]] = true;
						newValues.push_back(piatto + newValues[j]); //nuova somma trovata
					}
				}
				else if(piatto + newValues[j] < minimo)
					minimo = piatto + newValues[j];  //ok ho superato K ma magari è la soluzione migliore
			}
		}
	}
	

	fout<<minimo;
	return 0;
}

ora, potrebbe essere un errore mio ma è molto strano che i problemi di esempio vadano in locale e non online! ho letto di gente con lo stesso problema su altre piattaforme di allenamento ma qua non sto facendo nulla di così strano.
Semplicemente trovo tutte le somme possibili partendo da 0.
quindi 0 + n1
poi 0+n2 , n1+n2
poi 0+n3, n1+n3, n2+n3…
ovviamente usando la memoizzazione

SCUSATE IL LUNGO MESSAGGIO
sono storto io o cosa? con un altro miglioramento piccolino potrei finire in classifica


#2

Inizializza il vettore.


#3

Sono storto io o cosa?

Sono storto io