Submission #246314

#	Time	Username	Problem	Language	Result	Execution time	Memory
246314		alrad	Trener (COCI20_trener)	C++17	55 / 110	2058 ms	17404 KiB

trener

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()

const int N = 100 + 2;
const int MOD = 1e9 + 7;

int main() {
   #ifdef judge
      ifstream cin("input.txt");
   #endif // judge
   ios_base :: sync_with_stdio(0);
   cin.tie(0) , cout.tie(0);
   int n , k;
   cin >> n >> k;
   string full[n][k] , pref[n][k] , suf[n][k];
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < k; j++) {
         cin >> full[i][j];
         if (i > 0) {
            pref[i][j] = full[i][j].substr(0 , i);
            suf[i][j] = full[i][j].substr(1 , i);
         }
      }
   }
   vector<vector<int> > dp(n , vector<int>(k , 0));
   for (int j = 0; j < k; j++) {
      dp[0][j] = 1;
   }
   for (int i = 1; i < n; i++) {
      for (int cur = 0; cur < k; cur++) {
         for (int prev = 0; prev < k; prev++) {
            if (full[i - 1][prev] == pref[i][cur] || full[i - 1][prev] == suf[i][cur]) {
               dp[i][cur] += dp[i - 1][prev];
               dp[i][cur] %= MOD;
            }
         }
      }
   }
   int ans = 0;
   for (int j = 0; j < k; j++) {
      ans += dp[n - 1][j];
      ans %= MOD;
   }
   cout << ans << '\n';
   return 0;
}

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