# Aiuto Greedy Santa

**URL:** <https://forum.olinfo.it/t/aiuto-greedy-santa/5414>\
**Category:** Aiuto\
**Created:** [16 Novembre 2018, 9:51am UTC](https://forum.olinfo.it/t/aiuto-greedy-santa/5414 "2018-11-16T09:51:12Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![pm2001](https://forum.olinfo.it/user_avatar/forum.olinfo.it/pm2001/32/559_2.png) [@pm2001](https://forum.olinfo.it/u/pm2001)\
**Post date:** [16 Novembre 2018, 9:51am UTC](https://forum.olinfo.it/t/aiuto-greedy-santa/5414/1 "2018-11-16T09:51:13Z")

</div>

Ciao, ho scritto un codice per Greedy Santa, ottengo corrette tutte le subtasks tranne 2, probabilmente mi perdo qualcosa di ovvio, ma non lo trovo.  
Consigli?

```auto
#include <stdio.h>
#include <assert.h>
#include <iostream>
#define MAXN 100000
using namespace std;

int N, B, i,j;
int V,sum=0;
int arr[MAXN] { 0 };
int budget=0;
bool check = true;

int main() {

    cin >> N >> B;
    for(j=0; j<N; j++){
        cin >> V;
        sum+=V;
        arr[V]=1;
        for(i=B; i!=-1; i--){
            if(arr[i]==1&&i!=V)
                arr[i+V]=1;
    }
    }
    j=0;
    if(sum<=B)
    budget = sum;
    else
    for(i=0; check; i++){
        if(arr[B+i]==1){
            budget=B+i;
            break;
        }
    }

    printf("%d\n", budget);
    return 0;
}

```

---

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [16 Novembre 2018, 2:22pm UTC](https://forum.olinfo.it/t/aiuto-greedy-santa/5414/2 "2018-11-16T14:22:09Z")

</div>

Un caso che non consideri è quando ci sono più regali dello stesso prezzo.  
Input:

```
4 7
2 2 2 2

```

output:  
`8`  
Se ho capito bene utilizzi “arr” per segnarti se sei arrivato a quella determinata somma, quindi ti conviene mettere a vero il valore appena letto solo dopo aver aggiornato le somme raggiungibili. Fatto ciò non dovresti aver altri problemi.