Salve,
sto provando a risolvere il problema pranzo dalla nonna.
Purtroppo raggiungo solo 30/100 perché mi va in execution timed out negli ultimi 3 subtask.
Come posso rendere il mio codice più efficiente?
Devo capire come scartare permutazioni simili anziché testarle tutte. Qualche suggerimento?
#include <stdio.h>
#include <assert.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
#define MAXN 5000
#define MAXK 5000
#define MAXP 1000000
using namespace std;
int P[MAXN];
int main() {
FILE *fr, *fw;
int N, K, i, val;
vector<int>P;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(2 == fscanf(fr, "%d %d", &N, &K));
std::vector<int> a;
for(i=0; i<N; i++){
a.push_back(i);
assert(1 == fscanf(fr, "%d", &val));
P.push_back(val);
}
int min_totale = 100000000;
do{
int totale = 0;
for (int j=0;j<a.size(); j++){
int idx = a[j];
totale += P[idx];
if (totale >= K){
if (totale < min_totale){
min_totale = totale;
}
break;
}
}
}while (next_permutation(a.begin(), a.end()));
fprintf(fw, "%d\n", min_totale);
fclose(fr);
fclose(fw);
return 0;
}