Pranzo della nonna 60/100 Execution killed (could be triggered by violating memory limits)

Aiuto
1

Ciao a tutti, stavo cercando di risolvere questo problema ma non riesco a superare i 60 punti, qualche aiuto?
Questo è il codice:

#include <bits/stdc++.h>
using namespace std;

int N, M, i, j;
vector<vector<long long>> v;

int main() {
    ifstream cin("input.txt");
	ofstream cout("output.txt");
    cin >> N >> M;
    int c[N];
    for(; i < N; ++i) cin >> c[i];

    sort(c, c + N);
    
    vector<long long> t;
    v.push_back(t);
    v[0].push_back(0);
    
    for(i = 1; i <= N; ++i){
        v.push_back(t);  
        v[i].push_back(c[i - 1]);
    }
    
    for(i = 1; i <= N; ++i){
        
        for(j = 0; j < i; ++j){
            if(v[i][j] != v[j][0] + v[i][0]);
            v[i].push_back(v[j][0] + v[i][0]);
        }
        
        for(j = 0; j <= v[i - 1].size(); ++j){
            if(v[i][j] != v[i - 1][j] + v[i][0]);
            v[i].push_back(v[i - 1][j] + v[i][0]);
            
        }
    }
    long long ans = 1e18;
    for(i = N; i >= 1; --i){
        for(j = v[i].size() - 1; j >= 1; --j){
            if(v[i][j] < ans && v[i][j] >= M){
                ans = v[i][j];
            }
        }
    }
    cout << ans;
    return 0;
}
2

Ciao, il problema del tuo codice è che usa troppa memoria. Molto probabilmente deriva dalla grandezza del vettore V.

3

Ciao e grazie per la risposta, ho provato a migliorare il codice ma non riesco, potresti aiutarmi?

4

Il problema non è la dimensione dell’array ma il fatto che tu acceda a memoria non allocata. Se controlli bene c’è un ciclo for in cui fai j<=v[i-1].size() quando dovresti mettere solo <

1 Mi Piace
5

Grazie per avermelo fatto notare, ho migliorato il codice, rientra nei tempi ma alcune tasks sono errati, questo é il codice:

#include <bits/stdc++.h>
using namespace std;

int N, M, sum, i, j;
vector<vector<int>> v;

int main() {
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    
    
    cin >> N >> M;
    int c[N];
    for(; i < N; ++i) cin >> c[i];

    sort(c, c + N);
    
    vector<int> t;
    v.push_back(t);
    v[0].push_back(0);
    
    for(i = 1; i <= N; ++i){
        v.push_back(t);  
        v[i].push_back(c[i - 1]);
    }

    int ans = INT_MAX, a = 0;
    for(i = 1; i <= N; ++i){
        
        for(j = 1; j < i; ++j){
            if(v[i][v[i].size() - 1] < v[i - 1][j] + v[i][0] && v[i - 1][j] + v[i][0] < M)
            v[i].push_back(v[j][0] + v[i][0]);
            else if(abs(v[i - 1][j] + v[i][0] - M) < ans){
                ans = abs(v[i - 1][j] + v[i][0] - M);
                a = v[i - 1][j] + v[i][0];
            }
        }
        
        for(j = 0; j < v[i - 1].size(); ++j){
           if(v[i][v[i].size() - 1] < v[i - 1][j] + v[i][0]  && v[i - 1][j] + v[i][0] < M)
            v[i].push_back(v[i - 1][j] + v[i][0]);
            else if(abs(v[i - 1][j] + v[i][0] - M) < ans){
                ans = abs(v[i - 1][j] + v[i][0] - M);
                a = v[i - 1][j] + v[i][0];
            }
        }
    }
    cout << a;
    return 0;
}
6

Adesso sta a te trovare la tecnica risolutiva corretta. Qua sul forum ci sono già numerosi topic in cui si parla di questo problema. Puoi prendere spunto

1 Mi Piace