Pagini recente » Cod sursa (job #3249970) | Cod sursa (job #416447) | Cod sursa (job #223956) | Cod sursa (job #1919616) | Cod sursa (job #249510)
Cod sursa(job #249510)
#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;
}