oj.uz

Submission #845337

# Submission time Handle Problem Language Result Execution time Memory
845337 2023-09-06T13:13:01 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 237 ms 24480 KB 
#include <bits/stdc++.h>
using namespace std;
// bismillahirrahmanirrahim
int main() {
  int N, K;
  cin >> N >> K;
  vector<map<string, int>> cnt(N);
  for (int i = 0;i < N; ++i) {
    for (int j = 0;j < K; ++j) {
      string s;
      cin >> s;
      cnt[i][s] += 1;
    }
  }
  if (N == 1) {
    cout << K << '\n';
    return 0;
  }
  int64_t mod = 1e9+7;
  map<string, int64_t> dp;
  for (int i = N-1;i >= 0; --i) {
    for (auto [s, c] : cnt[i]) {
      if (i == N-1) {
        dp[s] = 1;
      }
      string a = s;
      string b = s;
      reverse(b.begin(), b.end());
      a.pop_back();
      b.pop_back();
      reverse(b.begin(), b.end());
      dp[a] += c * dp[s];
      if (a != b) dp[b] += c * dp[s];
      dp[a] %= mod;
      dp[b] %= mod;
    }
  }
  string s = "";
  int64_t ans = dp[s];
  cout << ans << '\n';
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 11 ms 1880 KB Output is correct
2 Correct 10 ms 1944 KB Output is correct
3 Correct 14 ms 1880 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 11 ms 1624 KB Output is correct
6 Correct 10 ms 1624 KB Output is correct
7 Correct 3 ms 344 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 11 ms 1880 KB Output is correct
6 Correct 10 ms 1944 KB Output is correct
7 Correct 14 ms 1880 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 11 ms 1624 KB Output is correct
10 Correct 10 ms 1624 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 225 ms 24468 KB Output is correct
13 Correct 237 ms 24404 KB Output is correct
14 Correct 224 ms 24400 KB Output is correct
15 Correct 223 ms 24480 KB Output is correct
16 Correct 50 ms 412 KB Output is correct
17 Correct 162 ms 16808 KB Output is correct
18 Correct 150 ms 17160 KB Output is correct
19 Correct 152 ms 17052 KB Output is correct
20 Correct 163 ms 16932 KB Output is correct
21 Correct 176 ms 16948 KB Output is correct
22 Correct 38 ms 444 KB Output is correct