# PBinfo #3448 – RecycleBin – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Se dă un șir de N numere întregi notat cu A. O subsecvență a șirului A este un șir Ai Ai+1 Ai+2 ... Aj cu 1 ≤ i ≤ j ≤ N, iar lungimea acestei subsecvențe este egală cu j – i + 1. O operație constă în alegerea unei subsecvențe din șir și ștergerea acesteia. În cadrul unei operații, lungimea subsecvenței alese trebuie să fie o putere de 2. În cadrul tuturor operațiilor efectuate pe șir, lungimile subsecvențelor șterse trebuie să fie distincte.

Pentru fiecare subsecvență din șir considerăm suma elementelor ei. Definim costul unui șir ca fiind maximul acestor sume, în cazul în care șirul conține cel puțin un număr pozitiv, altfel costul șirului este egal cu 0.

Putem aplica o succesiune de operații (eventual niciuna) pe șirul A. În urma acestor operații se vor șterge anumite elemente din șir, obținându-se astfel o mulțime de șiruri M={A, A’1 , A’2, A’3 , ...}.

Cerința
Să se determine costul maxim posibil ce se poate obține dintr-un șir al mulțimii M.

Date de intrare
Fișierul de intrare recyclebin.in conține pe prima linie un număr întreg N. A doua linie conține N numere întregi, separate prin câte un spațiu, reprezentând valorile șirului A.

Date de ieșire
Fișierul de ieșire recyclebin.out va conține pe prima linie valoarea costului maxim.

Restricții și precizări

1 ≤ N ≤ 1000
-106 ≤ Ai ≤ 106 pentru 1 ≤ i ≤ N
Pentru teste în valoare de 10 puncte 1 ≤ N ≤ 30
Pentru alte teste în valoare de 15 puncte se garantează că există o soluție cu cel mult o operație efectuată
Pentru alte teste în valoare de 20 puncte se garantează că există o soluție cu cel mult două operații efectuate
În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemplu.

Exemplu
recyclebin.in

14
13 -19 13 -5 -12 11 20 4 -10 1 -7 19 -19 3
recyclebin.out

76
Explicație
Șirul inițial este: [13 -19 13 -5 -12 11 20 (4 -10 1 -7) 19 -19 3].
De la poziția 8 ștergem 4 elemente, șirul rezultat este [13 -19 13 (-5 -12) 11 20 19 -19 3]
De la poziția 4 ștergem 2 elemente, șirul rezultat este [13 (-19) 13 11 20 19 -19 3].
De la poziția 2 ștergem un element, șirul rezultat este [13 13 11 20 19 -19 3].
Subsecvența de sumă maximă din șirul final este [13 13 11 20 19].

## Cod sursă C++

```cpp
/// stud. Theodor-Pierre Moroianu
/// Universitatea din Bucuresti
#include <bits/stdc++.h>
using namespace std;
const int VMAX = 1000000;
const int NMAX = 1000;
int solve(vector <int> v)
{
    vector <vector <int>> dp(v.size());
    int ans = 0;
    for (int i = 0; i < (int)v.size(); i++) {
        dp[i] = vector <int> (i + 2, 0);
        for (int j = 0; j <= i; j++) {
            dp[i][j] = v[i] + (i ? max(0, dp[i - 1][j]) : 0);
            ans = max(ans, dp[i][j]);
            for (int b = 1; b <= i; b *= 2)
                if (j & b)
                    dp[i][j] = max(dp[i][j], dp[i - b][j - b]);    
        }
    } 
    return ans;
}
int main()
{
    ifstream in("recyclebin.in");
    ofstream out("recyclebin.out");
    int n;
    in >> n;
    assert(n <= NMAX);
    vector <int> v(n);
    for (auto & i : v) {
        in >> i;
        assert(abs(i) <= VMAX);
    }
    out << solve(v) << '\n';
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3448)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3448/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3448/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)