제출 #1123271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123271		qrn	Trener (COCI20_trener)	C++20	22 / 110	23 ms	828 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 + 9;

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

    for (int i = 0; i <= m - n; i++) {
        if (s2.substr(i, n) == s1) {
            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])) {  
                    dp[i+1][jp1] += dp[i][j];
                    dp[i+1][jp1] %= mod;
                }
            }
        }
    }
    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: 0 / 33
• Subtask 3: 0 / 55