oj.uz

Submission #219337

# Submission time Handle Problem Language Result Execution time Memory
219337 2020-04-05T07:12:53 Z Vimmer Trener (COCI20_trener) C++14
55 / 110
 2000 ms 10912 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define F first
#define S second
#define sz(x) ll(x.size())
#define pb push_back
#define N 75005
#define M ll(1e9 + 7)

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;

//typedef tree<int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> oredered_set;



vector <int> g[N];

bool gd(string s, string p)
{
    for (int i = 0; i < sz(p); i++)
    {
        int j = 0;

        while (j < sz(s) && s[j] == p[j + i]) j++;

        if (j == sz(s)) return 1;
    }

    return 0;
}

ll dp[51][15001];

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, k;

    cin >> n >> k;

    int id = 0;

    int a[n][k];

    string s[n][k];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++) {cin >> s[i][j]; a[i][j] = id++;}

    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < k; j++)
            for (int x = 0; x < k; x++)
              if (gd(s[i][j], s[i + 1][x])) g[a[i][j]].pb(x);

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

    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < k; j++)
            for (auto it : g[a[i][j]]) dp[i + 1][it] = (dp[i + 1][it] + dp[i][j]) % M;

    ll ans = 0;

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

    cout << ans << endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2176 KB Output is correct
2 Correct 5 ms 2048 KB Output is correct
3 Correct 6 ms 2048 KB Output is correct
4 Correct 5 ms 2176 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3068 KB Output is correct
2 Correct 74 ms 2848 KB Output is correct
3 Correct 74 ms 2940 KB Output is correct
4 Correct 62 ms 5368 KB Output is correct
5 Correct 126 ms 3064 KB Output is correct
6 Correct 129 ms 3064 KB Output is correct
7 Correct 64 ms 5372 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2176 KB Output is correct
2 Correct 5 ms 2048 KB Output is correct
3 Correct 6 ms 2048 KB Output is correct
4 Correct 5 ms 2176 KB Output is correct
5 Correct 76 ms 3068 KB Output is correct
6 Correct 74 ms 2848 KB Output is correct
7 Correct 74 ms 2940 KB Output is correct
8 Correct 62 ms 5368 KB Output is correct
9 Correct 126 ms 3064 KB Output is correct
10 Correct 129 ms 3064 KB Output is correct
11 Correct 64 ms 5372 KB Output is correct
12 Execution timed out 2086 ms 10912 KB Time limit exceeded
13 Halted 0 ms 0 KB -