oj.uz

Submission #219371

# Submission time Handle Problem Language Result Execution time Memory
219371 2020-04-05T08:02:07 Z kartel Trener (COCI20_trener) C++14
110 / 110
 1148 ms 114760 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 2816 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 10368 KB Output is correct
2 Correct 15 ms 10240 KB Output is correct
3 Correct 15 ms 10496 KB Output is correct
4 Correct 16 ms 10880 KB Output is correct
5 Correct 15 ms 10752 KB Output is correct
6 Correct 15 ms 10752 KB Output is correct
7 Correct 16 ms 10880 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 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 10368 KB Output is correct
6 Correct 15 ms 10240 KB Output is correct
7 Correct 15 ms 10496 KB Output is correct
8 Correct 16 ms 10880 KB Output is correct
9 Correct 15 ms 10752 KB Output is correct
10 Correct 15 ms 10752 KB Output is correct
11 Correct 16 ms 10880 KB Output is correct
12 Correct 940 ms 108156 KB Output is correct
13 Correct 905 ms 108564 KB Output is correct
14 Correct 911 ms 108560 KB Output is correct
15 Correct 901 ms 108408 KB Output is correct
16 Correct 1148 ms 114760 KB Output is correct
17 Correct 956 ms 113400 KB Output is correct
18 Correct 967 ms 113252 KB Output is correct
19 Correct 961 ms 113220 KB Output is correct
20 Correct 974 ms 113304 KB Output is correct
21 Correct 988 ms 113388 KB Output is correct
22 Correct 1125 ms 114700 KB Output is correct