oj.uz

Submission #229361

# Submission time Handle Problem Language Result Execution time Memory
229361 2020-05-04T10:10:25 Z kartel Trener (COCI20_trener) C++14
110 / 110
 1116 ms 116748 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +400500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

bool go[51][1501][1501];
ll f[51][1501], ans, hsh[51][1501], p[51];
int i, j, k, m, p1, n;
string s[51][1501];

ll sm(ll x, ll y) {return (x + y) % M;}

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
//    in("input.txt");
//    out("output.txt");
    cin >> n >> m;
    p[0] = 1;
    for (i = 1; i <= n; i++) p[i] = (p[i - 1] * 31) % M;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            cin >> s[i][j];
            hsh[i][j] = 0;
            for (k = 0; k < i; k++)
                hsh[i][j] = sm(hsh[i][j], (s[i][j][k] - 'a' + 1) * p[k] % M);
        }
    for (i = 1; i < n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            for (k = 1; k <= m; k++)
            {
                if (hsh[i][j] * 31 % M == (hsh[i + 1][k] - (s[i + 1][k][0] - 'a' + 1) + M) % M) go[i][j][k] = 1;
                if (hsh[i][j] == (M + hsh[i + 1][k] - (s[i + 1][k][i] - 'a' + 1) * p[i] % M) % M) go[i][j][k] = 1;
            }
        }
    }
    for (i = 1; i <= m; i++) f[1][i] = 1;
    for (i = 1; i < n; i++)
        for (j = 1; j <= m; j++)
          for (k = 1; k <= m; k++)
            if (go[i][j][k]) f[i + 1][k] = sm(f[i][j], f[i + 1][k]);

    ans = 0;
    for (i = 1; i <= m; i++) ans = sm(f[n][i], ans);
    cout << ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10496 KB Output is correct
2 Correct 17 ms 10496 KB Output is correct
3 Correct 15 ms 10624 KB Output is correct
4 Correct 16 ms 11136 KB Output is correct
5 Correct 17 ms 10880 KB Output is correct
6 Correct 17 ms 10880 KB Output is correct
7 Correct 18 ms 11008 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 15 ms 10496 KB Output is correct
6 Correct 17 ms 10496 KB Output is correct
7 Correct 15 ms 10624 KB Output is correct
8 Correct 16 ms 11136 KB Output is correct
9 Correct 17 ms 10880 KB Output is correct
10 Correct 17 ms 10880 KB Output is correct
11 Correct 18 ms 11008 KB Output is correct
12 Correct 912 ms 110072 KB Output is correct
13 Correct 932 ms 110588 KB Output is correct
14 Correct 939 ms 110480 KB Output is correct
15 Correct 928 ms 110328 KB Output is correct
16 Correct 1115 ms 116748 KB Output is correct
17 Correct 942 ms 115428 KB Output is correct
18 Correct 989 ms 115184 KB Output is correct
19 Correct 977 ms 115300 KB Output is correct
20 Correct 979 ms 115276 KB Output is correct
21 Correct 948 ms 115312 KB Output is correct
22 Correct 1116 ms 116728 KB Output is correct