Submission #845515

#	Time	Username	Problem	Language	Result	Execution time	Memory
845515		vjudge1	Trener (COCI20_trener)	C++17	55 / 110	2047 ms	5980 KiB

trener

/**
 *  author: kututay
 *  created: 06.09.2023 16:41:38
**/
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
  #include "/Users/kutay/CP/templates/debug.h"
#else
  #define debug(...) void(38)
#endif

#define int long long

const int mod = 1e9 + 7;

int32_t main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, k; cin >> n >> k;
  vector<vector<string>> a(n, vector<string>(k));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      cin >> a[i][j];
    }
  }
  vector<vector<int>> dp(n, vector<int>(k, -1));

  for (int i = 0; i < k; i++) {
    dp[0][i] = 1;
  }

  for (int i = 1; i < n; i++) {
    for (int j = 0; j < k; j++) {
      int b = 0;
      for (int l = 0; l < k; l++) {
        if (a[i - 1][l] == a[i][j].substr(0, i) || a[i - 1][l] == a[i][j].substr(1, i)) {
          b += dp[i - 1][l];
          b %= mod;
        }
      }
      dp[i][j] = b % mod;
    }
  }
  int ans = 0;
  for (int i = 0; i < k; i++) {
    ans += dp[n - 1][i];
    ans %= mod;
  }
  cout << ans << '\n';
}

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