oj.uz

Submission #238356

# Submission time Handle Problem Language Result Execution time Memory
238356 2020-06-10T20:55:36 Z danikoynov Trener (COCI20_trener) C++14
55 / 110
 2000 ms 8104 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
const int MAXN = 55, MAXK = 1510;
const long long mod = 1e9 + 7;

int n, k;
long long dp[MAXN][MAXK];
string s[MAXN][MAXK];
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

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

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

    for (int i = 1; i < n; i ++)
        for (int j = 1; j <= k; j ++)
            for (int d = 1; d <= k; d ++)
            {
                string s1 = s[i][j], s2 = s[i + 1][d].substr(0, s[i + 1][d].size() - 1), s3 = s[i + 1][d].substr(1, s[i + 1][d].size() - 1);
                if (s1 == s2 || s1 == s3)
                    dp[i + 1][d] = (dp[i + 1][d] + dp[i][j]) % mod;
            }

    long long ans = 0;
    for (int j = 1; j <= k; j ++)
        ans = (ans + dp[n][j]) % mod;

    cout << ans << endl;
    return 0;
}

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 2944 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3456 KB Output is correct
2 Correct 62 ms 3576 KB Output is correct
3 Correct 68 ms 3576 KB Output is correct
4 Correct 56 ms 3456 KB Output is correct
5 Correct 65 ms 3456 KB Output is correct
6 Correct 67 ms 3448 KB Output is correct
7 Correct 57 ms 3448 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 6 ms 2944 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 61 ms 3456 KB Output is correct
6 Correct 62 ms 3576 KB Output is correct
7 Correct 68 ms 3576 KB Output is correct
8 Correct 56 ms 3456 KB Output is correct
9 Correct 65 ms 3456 KB Output is correct
10 Correct 67 ms 3448 KB Output is correct
11 Correct 57 ms 3448 KB Output is correct
12 Execution timed out 2077 ms 8104 KB Time limit exceeded
13 Halted 0 ms 0 KB -