Buongiorno, stavo provando a risolvere pranzo dalla nonna ma ottengo solo 60/100 e non capisco dove possa essere il problema.
Quello che faccio è:
ordino l’array, poi guardo ogni elemento, per ogni elemento guardo ogni ogni casella di count precedente, e memorizzo in count[i] la somma maggiore ottenibile che sia sotto a K oppure la somma minima che sia sopra K. Alla fine guardo ogni elemento e cerco il minore sopra K.
#include <assert.h>
#define MAXN 5000
#define MAXK 5000
#define MAXP 1000000
typedef int CmpFunType(const void *,const void *);
int CmpFun(const unsigned long long *v1, const unsigned long long *v2){
return (*v1 > *v2) - (*v2 > *v1);
}
unsigned long long P[MAXN],count[MAXN];
int main() {
FILE *fr, *fw;
int N, K, i,j;
unsigned long long r;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(2 == fscanf(fr, "%d %d", &N, &K));
for(i=0; i<N; i++)
assert(1 == fscanf(fr, "%llu", &P[i]));
qsort(P,N,sizeof(unsigned long long),(CmpFunType*)CmpFun);
for(i=0;i<N;++i){
count[i]=P[i];
for(j=0;j<i;++j){
if(count[i]<K){
count[i]= count[i]>count[j]+P[i]?count[i]:count[j]+P[i];
}else{
if(count[j]+P[i]>=K && count[j]+P[i]<count[i])count[i]=count[j]+P[i];
}
}
}
r=10000000000000;
for(i=0;i<N;++i){
if(count[i]>=K && count[i]<r)r=count[i];
}
fprintf(fw, "%llu\n", r);
fclose(fr);
fclose(fw);
return 0;
}