Nonna(Execution killed could be triggered by violatin memory limits)

Aiuto
1 
#include<iostream>
#include<algorithm> 
using namespace std;

int a[1005];
int f[100005];
int n,m;

int main(){
    freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int K, sum=0;
	cin>>n>>K;
	for (int i=1; i<=n; i++){
		cin>>a[i];
		sum+=a[i];
	}
	m=sum-K;
	for (int i=1; i<=n; i++){
		for (int j=m; j>=a[i]; j--){
			f[j]=max(f[j],f[j-a[i]]+a[i]);
		}
	}
	//for (int i=1; i<=m; i++) cout<<f[i]<<" "; cout<<endl; 
	int gm=sum-f[m];
	cout<<gm<<endl;
	return 0;
}

Sto risolvendo Pranzo dalla nonna, e non capisco perché mi esce execution killed. Qualcuno potrebbe aiutarmi? grazie.

2

Attento agli accessi fuori dai limiti, in particolare f[m] verso la fine.

3

Potresti specificare un po’, perché non ho capito molto bene qual è il problema e soprattutto come risolverlo. Grazie

4

potresti commentare il codice e la varie variabili? Cmq ti consiglierei di aumentare la dimensione del vettore a a 5000 come dicono le condizioni e nei cicli di partire da 0 e finire a n-1. Pero sapendo cosa siano m e f sarebbe piu facile capire il codice

5

non sono stato troppo a guardare il codice comunque stai dichiarando a con dimensione 1005 e poi lo stai scorrendo fino a n, tuttavia i costraints dicono 1<=N<=5000

6

Ho risolto grazie mille, anche se adesso mi da 80/100, per un ultimo test case execution timed out

8 
#include<iostream>
#include<algorithm> 
#include<vector>
#include<math.h>
#include<cstring>
using namespace std;

int f[100005];
int n,m;
int main(){
    freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int A[5000], temp[5000];
	int K, min=1000001, sum=0;
	cin>>n>>K;
	for (int i=0; i<n; i++){
		cin>>A[i];
		if(A[i]<min && A[i]>=K){
			min=A[i];
		}
		else{
			sum+=A[i];
		}
	}
	if(min!=1000001 && sum<K){
		cout<<min<<endl;
	}
	else{
		int x, j, plus=1;
		for(x=0;;x=x+plus){
			memset(f,0,100005); 
			for (int i=0; i<n; i++){
				for (j=K+x; j>=A[i]; j--){
					f[j]=max(f[j],f[j-A[i]]+A[i]);
				}
			}
			
			if(f[K+x]>=K)
				break;
		}
		cout<<f[K+x]<<endl;
	}
	return 0;
}

Questo è il nuovo programma e non so se posso velocizzarlo ancora, perché mi da il 33 testcase come execution timed out, il mio ragionamento è trovare il numero minore o uguale più vicino a K, e se il risultato è minore di K faccio K+1, finché non trovo il risultato. Non sono molto bravo a usare dp, quindi ho dovuto farlo in questo modo, qualcuno ha un suggerimento su come velocizzarlo? Grazie in anticipo.

9

Ti consiglio di seguire i consigli dati in un’altro forum sullo stesso problema: Pranzo dalla nonna (ottimizazione)
e inoltre per applicare i consigli e’ piu facile usare la ricorsione e una matrice globale