Pagini recente » Cod sursa (job #906381) | Cod sursa (job #1058066) | Cod sursa (job #1414767) | Cod sursa (job #1360968) | Cod sursa (job #466842)
Cod sursa(job #466842)
#include <cstdio>
#include <algorithm>
#define MAXN 500010
using namespace std;
int P, dp[MAXN], smax, i, j, sol, A[MAXN], V[MAXN];
int main ()
{
freopen ("congr.in", "r", stdin);
freopen ("congr.out", "w", stdout);
scanf ("%d\n", &P);
int n = 2 * P - 1;
for (i = 1; i <= n; i++)
scanf ("%d", &A[i]);
//sort (A + 1, A + n + 1);
dp[0] = 1;
for (i = 1; i <= n; i++)
for (j = smax; j >= 0; j--)
if (dp[j])
{
if (j + A[i] > smax)
smax = j + A[i];
if (V[j] + 1 > V[j + A[i]])
{
dp[j + A[i]] = i;
V[j + A[i]] = V[j] + 1;
if (V[j + A[i]] == P && (j + A[i]) % P == 0)
{
sol = j + A[i];
i = n + 1;
break;
}
}
}
while (sol)
{
printf ("%d ", dp[sol]);
sol = sol - A[dp[sol]];
}
return 0;
}