# Aiuto per The Indispensable Brick (ois\_tower)

**URL:** <https://forum.olinfo.it/t/aiuto-per-the-indispensable-brick-ois-tower/10034>\
**Category:** Aiuto\
**Created:** [24 Luglio 2026, 7:37am UTC](https://forum.olinfo.it/t/aiuto-per-the-indispensable-brick-ois-tower/10034 "2026-07-24T07:37:14Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![GNCNK](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gncnk/32/2751_2.png) [@GNCNK](https://forum.olinfo.it/u/GNCNK)\
**Post date:** [24 Luglio 2026, 7:37am UTC](https://forum.olinfo.it/t/aiuto-per-the-indispensable-brick-ois-tower/10034/1 "2026-07-24T07:37:14Z")

</div>

Ciao a tutti, ho bisogno di aiuto per risolvere il problema [The Indispensable Brick](https://training.olinfo.it/task/ois_tower).

Il mio codice funziona. Ma è troppo lento per andare sotto 1 secondo. Purtroppo non so come ottimizzarlo qualcuno mi potrebbe aiutare?

Ecco il mio codice:

```cpp
// NOTE: it is recommended to use this even if you don't understand the following code.

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

bool isPossible(vector<int> numbers, int S) {
    bool dp[S+1] = {false};
    dp[0] = true;

    for (int number:numbers) {
        for (int j=S; j >= number; j--) {
            if (dp[j-number]) {
                dp[j] = true;
            }
        }
    }

    return dp[S];
}

int main() {
    // uncomment the two following lines if you want to read/write from files
    // ifstream cin("input.txt");
    // ofstream cout("output.txt");

    int N, S;
    cin >> N >> S;

    vector<int> H(N);
    for (int i = 0; i < N; ++i)
        cin >> H[i];

    vector<bool> ans(N);

    // INSERT YOUR CODE HERE

    for (int i=0; i<N; i++) {
        int number = H[0];
        H.erase(H.begin());
        ans[i] = not isPossible(H, S);
        H.push_back(number);
    }

    for (int i = 0; i < N; ++i) {
        if (ans[i]) {
            cout << "YES";
        } else {
            cout << "NO";
        }

        cout << endl;
    }
    return 0;
}

```

Grazie mille in anticipo!

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/2615_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [24 Luglio 2026, 9:36am UTC](https://forum.olinfo.it/t/aiuto-per-the-indispensable-brick-ois-tower/10034/2 "2026-07-24T09:36:36Z")

</div>

Ti serve un trucco per evitare di fare knapsack N volte: riesci a riscrivere la condizione come condizione su un prefisso + condizione su un suffisso dell’array?  
Se no forse con i bitset passa anche \mathcal{O}(N^2S).