Submission #1123274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123274		qrn	Trener (COCI20_trener)	C++17	55 / 110	2090 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;

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

    intt l = 0, r = n - 1;
    string cur = "";
    for(int i = l; i <= r; i++) cur += s2[i];
    while(r < m) {
        // cout << cur << " " << s1 << " " << s2 << endl;
        if(cur == s1) {
            return true;
        } else {
            r++;
            cur += s2[r];
            cur.erase(cur.begin());
        }
    }
    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