Pagini recente » Cod sursa (job #738693) | Cod sursa (job #3154490) | Cod sursa (job #3221851) | Cod sursa (job #3125787) | Cod sursa (job #2427044)
#include <cstdio>
#define MOD 666013
#define DIMN 510
#define VALMAX 510
using namespace std;
int s1[DIMN],s2[DIMN],s3[DIMN];
int aib[2][VALMAX] , d[2][DIMN][DIMN],aux[2][DIMN][DIMN];
inline void update (int tip,int p,int val){
int i;
if (!val)
return;
for (i = p;i<VALMAX;i = i + ( i & (-i))){
aib[tip][i] =aib[tip][i] + val;
if (aib[tip][i]>=MOD)
aib[tip][i]-=MOD;
}
}
int query (int tip,int p){ /// vrei cu linia mai mica decat l si val < p
int i;
int sol = 0;
if (!p)
return 0;
for (i = p;i>0;i = i - ( i & (-i))){
sol =sol + aib[tip][i];
if (sol>=MOD)
sol-=MOD;
}
return sol;
}
int main()
{
FILE *fin=fopen ("pedefe.in","r");
FILE *fout=fopen ("pedefe.out","w");
int n,m,p,i,j,k,sol=0,x,x2;
fscanf (fin,"%d%d%d",&n,&m,&p);
for (i=1;i<=n;i++)
fscanf (fin,"%d",&s1[i]);
for (i=1;i<=m;i++)
fscanf (fin,"%d",&s2[i]);
for (i=1;i<=p;i++)
fscanf (fin,"%d",&s3[i]);
/// d[i][j][k] = nr de solutii daca ai 1..i din s1 , 1..j din s2 , si 1..k din s3
s3[0] = -1;
s3[p+1] = VALMAX - 1;
for (k=0;k<=p;k++){
x = (k%2);
for (i=1;i<=n;i++){
if (k<=1)
update (0,1,1);
for (j=1;j<=m;j++){
x2 = 0;
if (s1[i] == s2[j]){
if (s1[i] == s3[k]) /// suma d[p][r][k-1] unde s1[p]==s2[r]<=s3[k]
x2 = query ( 1 - x , s1[i]);
else if (s1[i] > s3[k])
x2 = query ( x , s1[i]);
if (k==p){
sol = sol + x2;
if (sol>=MOD)
sol-=MOD;
}
}
d[x][i][j] = x2;
if (s1[i] <= s3[k+1]){ /// nu ai cum altfel
update (1 - x , s1[i] , aux[1 - x][i-1][j]);
update ( x , s1[i] , aux[x][i-1][j]);
/// tocmai ai scapat de j pe linia i, il adaugi pt j ul de pe linia i+1
aux[1 - x][i][j] = aux[1 - x][i-1][j] + d[1 - x][i][j];
if (aux[1-x][i][j] >=MOD)
aux[1-x][i][j]-=MOD;
aux[x][i][j] = aux[x][i-1][j] + d[x][i][j];
if (aux[x][i][j] >=MOD)
aux[x][i][j]-=MOD;
}
}
for (j=1;j<VALMAX;j++)
aib[0][j] = aib[1][j] = 0;
}
}
fprintf (fout,"%d",sol);
return 0;
}