Cod sursa(job #2633830)

Utilizator alexradu04Radu Alexandru alexradu04 Data 8 iulie 2020 19:31:35
Problema Pedefe Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb

#include <bits/stdc++.h>
#define maxn 505
#define mod 666013
std::ifstream fin ("pedefe.in");
std::ofstream fout ("pedefe.out");

long long x1[maxn];
long long x2[maxn];
long long x3[maxn];

long long dp[2][maxn][maxn];
long long sum[maxn];
long long bit[maxn];

void update (long long *arr, long long pos, long long val){
    if (val == 0)
        return;
    while (pos < maxn){
        arr[pos] += val;
        pos = (pos | (pos+1));
    }
}

long long query (long long *arr, long long pos){
    long long ans = 0;
    while (pos >= 0){
        ans += arr[pos];
        pos = (pos & (pos+1)) - 1;
    }
    return ans;
}

int main(){

    int n1, n2, n3, i, j ,k, ii, jj, kk;
    fin >> n1 >> n2 >> n3;
    for (i=1; i<=n1; i++)
        fin >> x1[i];
    for (i=1; i<=n2; i++)
        fin >> x2[i];
    for (i=1; i<=n3; i++)
        fin >> x3[i];

    dp[0][0][0] = 1;
    int crt = 1, ok = 1;
    for (k=0; k<=n3; k++){
        memset (sum, 0, sizeof sum);
        memset (dp[1-crt], 0, sizeof dp[1-crt]);
        for (i=1; i<=n1; i++){
            memset (bit, 0, sizeof bit);
            for (j=1; j<=n2; j++){
                if (x1[i] == x2[j]){
                    if (x1[i] == x3[k+1])
                        dp[1-crt][i][j] = (dp[1-crt][i][j] + query (bit, x1[i]) + ok);
                    else
                        dp[crt][i][j] = (dp[crt][i][j] + query (bit, x1[i] + ok));

                }
                update (bit, x2[j], sum[j]);
                sum[j] = (sum[j] + dp[crt][i][j]);
            }
        }
        crt = 1-crt;
        if (ok == 1) ok =  0;
    }

    /*
    for (k=1; k<=n3; k++){
        for (i=1; i<=n1; i++, fout << '\n')
            for (j=1; j<=n2; j++)
            fout << dp[k][i][j] << ' ';
        fout << "**********\n";
    }
    */

    long long ans = 0;
    for (i=1; i<=n1; i++)
        for (j=1; j<=n2; j++)
            ans = ans + dp[1-crt][i][j];

    fout << ans % mod << '\n';

    return 0;
}