Cod sursa(job #466842)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 27 iunie 2010 18:34:50
Problema Congr Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#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;
}