oj.uz

Submission #219342

# Submission time Handle Problem Language Result Execution time Memory
219342 2020-04-05T07:16:49 Z Vimmer Trener (COCI20_trener) C++14
55 / 110
 2000 ms 5792 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;


bool gd(string s, string p)
{
    for (int i = 0; i <= sz(p) - sz(s); 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][1501];

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;

    string s[n][k];

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

    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 (int u = 0; u < k; u++) if (gd(s[i][j], s[i + 1][u])) dp[i + 1][u] = (dp[i + 1][u] + 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 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 888 KB Output is correct
2 Correct 42 ms 908 KB Output is correct
3 Correct 42 ms 896 KB Output is correct
4 Correct 48 ms 888 KB Output is correct
5 Correct 51 ms 888 KB Output is correct
6 Correct 51 ms 888 KB Output is correct
7 Correct 49 ms 896 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 42 ms 888 KB Output is correct
6 Correct 42 ms 908 KB Output is correct
7 Correct 42 ms 896 KB Output is correct
8 Correct 48 ms 888 KB Output is correct
9 Correct 51 ms 888 KB Output is correct
10 Correct 51 ms 888 KB Output is correct
11 Correct 49 ms 896 KB Output is correct
12 Execution timed out 2088 ms 5792 KB Time limit exceeded
13 Halted 0 ms 0 KB -