Submission #246319

#	Time	Username	Problem	Language	Result	Execution time	Memory
246319		alrad	Trener (COCI20_trener)	C++17	110 / 110	796 ms	3576 KiB

trener

#include <bits/stdc++.h>

using namespace std;

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

const long long P = 31;
const long long HashMod = 1e9 + 123;
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;
   vector<long long> pow;
   pow.push_back(1LL);
   while ((int)pow.size() <= n) {
      pow.push_back(1LL * pow.back() * P % MOD);
   }
   auto getHash = [&](string s) {
      int res = 0;
      for (int i = 0; i < (int)s.size(); i++) {
         res += ((1LL * s[i] * pow[i]) % MOD);
         res %= MOD;
      }
      return res;
   };
   int full[n][k] , pref[n][k] , suf[n][k];
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < k; j++) {
         string x;
         cin >> x;
         full[i][j] = getHash(x);
         if (i > 0) {
            pref[i][j] = getHash(x.substr(0 , i));
            suf[i][j] = getHash(x.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: 55 / 55