oj.uz

Submission #845292

# Submission time Handle Problem Language Result Execution time Memory
845292 2023-09-06T13:01:51 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 234 ms 4872 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 2e5 + 5, MOD = 1e9 + 7, p = 29, p1 = 37;

ll dp[55][1505], h[2][55][1505][3], us[60], us2[60];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    us[0] = 1;
    us2[0] = 1;

    for(int i = 1; i < 60; i++)
    {
        us[i] = (us[i - 1] * p) % MOD;
        us2[i] = (us2[i - 1] * p1) % MOD;
    }

    int n, k;
    cin >> n >> k;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            string str;
            cin >> str;

            str = "#" + str;

            for(int l = 1; l <= i; l++)
            {
                h[0][i][j][0] = (h[0][i][j][0] + (str[l] - 'a' + 1) * us[l]) % MOD;              
                h[1][i][j][0] = (h[1][i][j][0] + (str[l] - 'a' + 1) * us2[l]) % MOD;
                if(l == i - 1)
                {
                    h[0][i][j][1] = h[0][i][j][0];
                    h[1][i][j][1] = h[1][i][j][0];
                }
            }

            for(int l = 2; l <= i; l++)
            {
                h[0][i][j][2] = (h[0][i][j][2] + (str[l] - 'a' + 1) * us[l - 1]) % MOD;
                h[1][i][j][2] = (h[1][i][j][2] + (str[l] - 'a' + 1) * us2[l - 1]) % MOD;
            }

     //       cout << i << " " << j << " " << h[i][j][0] << " " << h[i][j][1] << " " << h[i][j][2] << '\n';
        }
    }

    for(int i = 1; i <= k; i++)
        dp[1][i] = 1;

    for(int i = 1; i < n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            for(int l = 1; l <= k; l++)
            {
                if(h[0][i][j][0] == h[0][i + 1][l][1] and h[1][i][j][0] == h[1][i + 1][l][1])
                {
                    if(dp[i + 1][l] == 0)
                    {
                        dp[i + 1][l] = dp[i][j];
                    }
                    else
                    {
                        dp[i + 1][l] = (dp[i + 1][l] + dp[i][j]) % MOD;
                    }
                }
                else if(h[0][i][j][0] == h[0][i + 1][l][2] and h[1][i][j][0] == h[1][i + 1][l][2])
                {
                    if(dp[i + 1][l] == 0)
                    {
                        dp[i + 1][l] = dp[i][j];
                    }
                    else
                    {
                        dp[i + 1][l] = (dp[i + 1][l] + dp[i][j]) % MOD;
                    }
                }
            }
        }
    }

    // for(int i = 1; i <= n; i++)
    // {
    //     for(int j = 1; j <= k; j++)
    //     {
    //         cout << dp[i][j] << " " ;
    //     }
    //     cout << '\n';
    // }

    ll ans = 0;

    for(int i = 1; i <= k; i++)
        ans = (ans + dp[n][i]) % MOD;

    cout << ans << '\n';
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 3 ms 1116 KB Output is correct
4 Correct 3 ms 1116 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 1112 KB Output is correct
12 Correct 133 ms 4492 KB Output is correct
13 Correct 133 ms 4692 KB Output is correct
14 Correct 132 ms 4688 KB Output is correct
15 Correct 132 ms 4512 KB Output is correct
16 Correct 220 ms 4504 KB Output is correct
17 Correct 139 ms 4692 KB Output is correct
18 Correct 142 ms 4688 KB Output is correct
19 Correct 145 ms 4872 KB Output is correct
20 Correct 141 ms 4512 KB Output is correct
21 Correct 139 ms 4512 KB Output is correct
22 Correct 234 ms 4596 KB Output is correct