oj.uz

Submission #845515

# Submission time Handle Problem Language Result Execution time Memory
845515 2023-09-06T13:57:53 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 5980 KB 
/**
 *  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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 600 KB Output is correct
2 Correct 21 ms 856 KB Output is correct
3 Correct 21 ms 832 KB Output is correct
4 Correct 11 ms 604 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 21 ms 604 KB Output is correct
7 Correct 14 ms 604 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 21 ms 600 KB Output is correct
6 Correct 21 ms 856 KB Output is correct
7 Correct 21 ms 832 KB Output is correct
8 Correct 11 ms 604 KB Output is correct
9 Correct 21 ms 604 KB Output is correct
10 Correct 21 ms 604 KB Output is correct
11 Correct 14 ms 604 KB Output is correct
12 Execution timed out 2047 ms 5980 KB Time limit exceeded
13 Halted 0 ms 0 KB -