concurs

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

int n, v[1001], s[1001], suma_max, x, y, ap[1001];

void reconstituire(int suma)
{
    stack<int> elemente;

    for(int i = suma; i != 0; i = (i-v[s[i]]))
        if(ap[s[i]] == 0)
        elemente.push(s[i]), ap[s[i]] = 1;

    while(!elemente.empty())
        cout << elemente.top() << ' ', elemente.pop();

    cout << '\n';
}

int main()
{
    freopen("concurs.in", "r", stdin);
    freopen("concurs.out", "w", stdout);

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i], suma_max += v[i]; /// citesc elementele si gasesc suma maxima

    memset(s, 1, sizeof(s)); /// initializez array-ul de suma
    s[0] = 0;

    for(int i = 1; i <= n; i++)/// parcurg fiecare element
        for(int j = 0; j <= suma_max-v[i]; j++) /// parcurg fiecare suma de la 0 la suma_max - elementul deoarece nu vreau sa formez o suma mai mare
            if(s[j] < i)/// daca indicele elementului cu care am format suma este mai mic decat indicele curent
                s[j+v[i]] = i; /// formez suma dintre element si indice

    x = suma_max/2; /// caut sumele de mijloc
    y = suma_max/2;

    while(s[x] == maxim) /// cat timp nu pot forma suma x
        x--; /// scad x si caut o suma mai mica

//    while(s[y] == maxim) /// cat timp nu pot forma suma y
//        y++; /// cresc y si caut o suma mai mare pe care o pot forma
    y = suma_max - x;


    cout << x << '\n';
    reconstituire(x);

    cout << y << '\n';
    reconstituire(y);
}