Cod sursa(job #249510)

Utilizator coderninuHasna Robert coderninu Data 28 ianuarie 2009 17:19:31
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>
#define Nmax 5001


inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }

int A[Nmax], B[Nmax], c[Nmax][Nmax], st[Nmax*2+1], i, j, N, M, m, dir;

int main()
{
	freopen("zeratul.in", "r", stdin);
	for(scanf("%d\n", &N), i = 1; i<=N; ++i) scanf("%d ", A + i);
	for(scanf("%d\n", &M), i = 1; i<=M; ++i) scanf("%d ", B + i);
	for (i = 1; i<=N; ++i) c[i][1] = c[i-1][1] + A[i]*B[1];
	for (i = 2; i<=M; ++i) c[1][i] = c[1][i-1] + A[1]*B[i];
	for (i = 2; i<=N; ++i)
		for (j = 2; j <= M; ++j)
			c[i][j] = A[i]*B[j] + max(c[i-1][j], max(c[i][j-1],c[i-1][j-1]));
	freopen("zeratul.out", "w", stdout);
	printf("%d\n", c[N][M]);
	for (i = 0; N != 1 || M!=1; )
	{
		dir = 0; m =c[N-1][M];
		if (c[N][M-1] > m) { m = c[N][M-1]; dir = 1; }
		if (c[N-1][M-1] > m) { m = c[N-1][M-1]; dir = 2; }
		st[++i] = dir;
		if (!dir) --N;
		else if (dir == 1) --M;
		else { --N; --M; }
	}
	for ( ; i; --i ) printf("%c", st[i]+'A');
	return 0;
}