oj.uz

Submission #999013

# Submission time Handle Problem Language Result Execution time Memory
999013 2024-06-15T05:00:23 Z vjudge1 Trener (COCI20_trener) C++17
0 / 110
 19 ms 1456 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 55, K = 1505;
const ll base = 727, mod = 1e9 + 7;

ll n, k;
map<string, ll> cnt[N], dp[N];

int main(){
    cin >> n >> k;
    for (ll i = 1; i <= n; i ++){
        for (ll j = 1; j <= k; j ++){
            string s;
            cin >> s;

            cnt[i][s]++;
            dp[i][s]++;
        }
    }

    // cout << endl;
    // for (int i = 1; i <= n; i ++){
    //     cout << i << " : ";
    //     for (auto [H, val] : dp[i])
    //         cout << H << " -- " << val << ", ";
    //     cout << endl;
    // }
    // cout << endl;

    for (ll i = n - 1; i > 0; i --){
        for (auto [S, C] : cnt[i]){
            ll sm = 0;
            // cout << "HASH = " << H << endl;
            string pref = S + '#';
            string suff = '#' + S;
            for (int c = 'a'; c <= 'z'; c ++){
                // cout << "can have edge with " << nh << endl;
                pref[i] = suff[0] = c;

                if (dp[i + 1].find(pref) != dp[i + 1].end())
                    sm = (sm + dp[i + 1][pref]) % mod;

                if (dp[i + 1].find(suff) != dp[i + 1].end())
                    sm = (sm + dp[i + 1][suff]) % mod;
            }

            dp[i][S] = C * sm % mod;
        }
    }

    // cout << endl;
    // for (int i = 1; i <= n; i ++){
    //     cout << i << " : ";
    //     for (auto [H, val] : dp[i])
    //         cout << H << " -- " << val << ", ";
    //     cout << endl;
    // }
    // cout << endl;

    ll ans = 0;
    for (auto [S, val] : dp[1])
        ans = (ans + val) % mod;
    cout << ans << endl;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1372 KB Output is correct
2 Correct 19 ms 1372 KB Output is correct
3 Correct 18 ms 1456 KB Output is correct
4 Incorrect 3 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -