# Cod sursa(job #152924)

Utilizator Data 9 martie 2008 22:05:08 Pedefe 20 cpp done Arhiva de probleme 1.69 kb
``````#include <fstream>
#include <algorithm>

using namespace std;

const char iname[] = "pedefe.in";
const char oname[] = "pedefe.out";

#define FOR(i, a, b)  for (int i = (a); i <= (b); ++ i)
#define FORR(i, b, a) for (int i = (b); i >= (a); -- i)
#define FORi(i, G)    for (vector <int>::iterator i = G.begin(); i != G.end(); ++ i)

#define MAXN  505

#define modulo 666013

int A[MAXN], B[MAXN], C[MAXN];

int Cnt[2][MAXN][MAXN], Sum[2][MAXN][MAXN];

inline void update(int &var, int val) {
if ((var += val) >= modulo)
var -= modulo;
}

int main(void)
{
ifstream fin(iname);

int n, m, p;

fin >> n >> m >> p;
FOR (i, 1, n)
fin >> A[i];
FOR (i, 1, m)
fin >> B[i];
FOR (i, 1, p)
fin >> C[i];

fin.close();

int s = 0;

Cnt[s][0][0] = Sum[s][0][0] = 1;

FOR (i, 1, n)
{
FOR (j, 1, m) if (A[i] == B[j])
FOR (p, 0, i-1) if (A[p] <= A[i])
update(Cnt[s][i][j], Sum[s][p][0] - Sum[s][p][j]);

Sum[s][i][m] = Cnt[s][i][m];
FORR (j, m - 1, 0)
update(Sum[s][i][j], Cnt[s][i][j] + Sum[s][i][j + 1]);
}

FOR (k, 1, p)
{
s = k & 1;
memset(Cnt[s], 0, sizeof(Cnt[s])), memset(Sum[s], 0, sizeof(Sum[s]));

FOR (i, 1, n)
{
FOR (j, 1, m) if (A[i] == B[j])
{
int which = (A[i] == C[k]) ? (s ^ 1) : s;
FOR (p, 0, i-1) if (A[p] <= A[i])
update(Cnt[s][i][j], Sum[which][p][0] - Sum[which][p][j]);
}

Sum[s][i][m] = Cnt[s][i][m];
FORR (j, m - 1, 0)
update(Sum[s][i][j], Cnt[s][i][j] + Sum[s][i][j + 1]);
}
}

int ret = 0;

FOR (i, 1, n) FOR (j, 1, m) if (A[i] == B[j])
update(ret, Cnt[p & 1][i][j]);

ofstream fout(oname);	fout << ret <<'\n';  fout.close();

return 0;
}
``````