oj.uz

Submission #464822

# Submission time Handle Problem Language Result Execution time Memory
464822 2021-08-14T09:33:41 Z TheScrasse Trener (COCI20_trener) C++17
110 / 110
 832 ms 43972 KB 
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 1000000007
#define hmod 10000000000037
#define maxn 60
#define maxm 1510

ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll hx, hp[maxn], hc[maxn], hs[maxn][maxm][maxn];
ll dp[maxn][maxm];
string mt[maxn][maxm];

int main() {
    mt19937 rng(19938);

    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    for (i = 0; i <= 25; i++) {
        hc[i] = uniform_int_distribution<ll>(1000 * i, 1000 * i + 999)(rng);
    }
    hx = uniform_int_distribution<ll>(30001, 40000)(rng);
    hp[0] = 1;
    for (i = 1; i < maxn; i++) hp[i] = (hx * hp[i - 1]) % hmod;

    cin >> n >> m;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            cin >> mt[i][j];
        }
    }

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            for (k = 1; k <= i; k++) {
                hs[i][j][k] = (hs[i][j][k - 1] + hp[k - 1] * hc[(ll)mt[i][j][k - 1] - 'a']) % hmod;
            }
        }
    }

    for (j = 1; j <= m; j++) dp[1][j] = 1;
    for (i = 2; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            for (k = 1; k <= m; k++) {
                if (hs[i][j][i - 1] == hs[i - 1][k][i - 1] ||
                    (hs[i][j][i] - hs[i][j][1] - hx * hs[i - 1][k][i - 1]) % hmod == 0) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
                }
            }
            if (i == n) res = (res + dp[i][j]) % mod;
        }
    }

    /* for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            cout << dp[i][j] << ' ';
        }
        cout << nl;
    } */

    cout << res << nl;

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3160 KB Output is correct
3 Correct 2 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6220 KB Output is correct
2 Correct 6 ms 6220 KB Output is correct
3 Correct 6 ms 6220 KB Output is correct
4 Correct 8 ms 6220 KB Output is correct
5 Correct 7 ms 6220 KB Output is correct
6 Correct 7 ms 6220 KB Output is correct
7 Correct 9 ms 6244 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3160 KB Output is correct
3 Correct 2 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct
5 Correct 6 ms 6220 KB Output is correct
6 Correct 6 ms 6220 KB Output is correct
7 Correct 6 ms 6220 KB Output is correct
8 Correct 8 ms 6220 KB Output is correct
9 Correct 7 ms 6220 KB Output is correct
10 Correct 7 ms 6220 KB Output is correct
11 Correct 9 ms 6244 KB Output is correct
12 Correct 307 ms 43788 KB Output is correct
13 Correct 290 ms 43748 KB Output is correct
14 Correct 307 ms 43900 KB Output is correct
15 Correct 296 ms 43700 KB Output is correct
16 Correct 831 ms 43824 KB Output is correct
17 Correct 316 ms 43748 KB Output is correct
18 Correct 313 ms 43760 KB Output is correct
19 Correct 321 ms 43704 KB Output is correct
20 Correct 320 ms 43972 KB Output is correct
21 Correct 316 ms 43712 KB Output is correct
22 Correct 832 ms 43772 KB Output is correct