Submission #1306705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306705		nguyenkhangninh99	Trener (COCI20_trener)	C++20	110 / 110	88 ms	7196 KiB

trener

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7; 

signed main(){ 
    int n, k; cin >> n >> k;
    vector<vector <int>> dp(n + 1, vector<int>(k + 1));
    vector<vector<string>> inp(n + 1, vector<string>(k + 1));
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= k;j++) cin >> inp[i][j];
    }
    for(int i = 1;i <= k;i++) dp[1][i] = 1;
    for(int i = 2;i <= n;i++){
        map <string, int> cnt;
        for(int j = 1;j <= k;j++){
            cnt[inp[i - 1][j]] += dp[i - 1][j];
            cnt[inp[i - 1][j]] %= mod;
        }
        for(int j = 1;j <= k;j++){
            string a = inp[i][j].substr(0, i - 1);
            string b = inp[i][j].substr(1, i - 1);
            if(a != b) dp[i][j] = (cnt[a] + cnt[b]) % mod;
            else dp[i][j] = cnt[a];
        }
    }
    int ans = 0;
    for(int i = 1;i <= k;i++) (ans += dp[n][i]) %= mod;
    cout << ans;
}

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