Submission #1123275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123275		qrn	Trener (COCI20_trener)	C++17	55 / 110	2095 ms	5960 KiB

trener

#include <bits/stdc++.h>
using namespace std;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ALL(x) x.begin(), x.end()
#define intt long long
#define int long long
#define endl "\n"

const intt mod = 1e9 + 7, base = 31;

bool check(const string& s1, const string& s2) {
    int n = s1.size(), m = s2.size();
    if (n > m) return false;

    intt s1h = 0, hashw = 0, p = 1;

    for (int i = 0; i < n; i++) {
        s1h = (s1h * base + s1[i]) % mod;
        hashw = (hashw * base + s2[i]) % mod;
        if (i < n - 1) p = (p * base) % mod; 
    }

    if (s1h == hashw && s1 == s2.substr(0, n)) {
        return true;
    }

    for (int i = n; i < m; i++) {
        hashw = (hashw - s2[i - n] * p % mod + mod) % mod;
        hashw = (hashw * base + s2[i]) % mod;

        if (s1h == hashw && s1 == s2.substr(i - n + 1, n)) {
            return true;
        }
    }

    return false;
}


void solve()  {
    // dp[i][j] -> i-cideyik, j-ci stringi secmisik, L ads
    intt n, m;
    cin >> n >> m;
    vector<vector<string>>g(n + 1, vector<string>(m + 1));

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }

    vector<vector<intt>>dp(n + 1, vector<intt>(m + 1, 0));
    for(int j = 1; j <= m; j++) {
        dp[1][j] = 1;
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= m; j++){
            for(int jp1 = 1; jp1 <= m; jp1++) {
                if(check(g[i][j], g[i+1][jp1])) {  
                    // cout << i << " " << j << "  " << i+1 << " " << jp1 << endl;
                    dp[i+1][jp1] += dp[i][j];
                    dp[i+1][jp1] %= mod;
                }
            }
        }
    }
    // cout << endl;
    intt ans  = 0;
    // for(int i = 1; i <= n; i++) {
    //     for(int j = 1; j <= m; j++) {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    for(int i = 1; i <= m; i++) {
        ans += dp[n][i];
        ans %= mod;
    }
    cout << ans << endl;
}

signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 55