Cod sursa(job #2636300)

Utilizator giotoPopescu Ioan gioto Data 17 iulie 2020 14:39:06
Problema Pedefe Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
using namespace std;

const int DIM = 502;
const int INF = 1005;
const int MOD = 666013;

int n, m, p;
int dp[2][DIM][101];
int s1[DIM], s2[DIM], s3[105];

int main()
{
    freopen("pedefe.in", "r", stdin);
    freopen("pedefe.out", "w", stdout);

    scanf("%d%d%d", &n, &m, &p);

    for (int i = 1; i <= n ; ++i) scanf("%d", &s1[i]);
    for (int i = 1; i <= m ; ++i) scanf("%d", &s2[i]);
    for (int i = 1; i <= p ; ++i) scanf("%d", &s3[i]);

    s3[p + 1] = INF;
    dp[0][0][0] = 1;
    for (int i = 0, l = 0; i <= n ; ++i, l = 1 - l) {
        for (int j = 0; j <= m ; ++j) {
            for (int k = 0; k <= p ; ++k) {
                if (i == 0 && j == 0 && k == 0) continue ;

                if (i > 0 && j > 0 && s1[i] == s2[j] && s1[i] >= s3[k] && s1[i] <= s3[k + 1])
                    dp[l][j][k] += dp[1 - l][j - 1][k];

                if (i > 0 && j > 0 && k > 0 && s1[i] == s2[j] && s1[i] == s3[k])
                    dp[l][j][k] += dp[1 - l][j - 1][k - 1];

                if (i > 0) dp[l][j][k] += dp[1 - l][j][k];
                if (j > 0) dp[l][j][k] += dp[l][j - 1][k];

                if (i > 0 && j > 0) dp[l][j][k] -= dp[1 - l][j - 1][k];

                while (dp[l][j][k] >= MOD) dp[l][j][k] -= MOD;
                while (dp[l][j][k] < 0) dp[l][j][k] += MOD;
            }
        }

        memset(dp[1 - l], 0, sizeof(dp[1 - l]));
    }

    printf("%d", dp[n & 1][m][p]);

    return 0;
}