oj.uz

Submission #1006378

# Submission time Handle Problem Language Result Execution time Memory
1006378 2024-06-23T22:54:15 Z MilosMilutinovic Trener (COCI20_trener) C++14
110 / 110
 82 ms 3168 KB 
#include <bits/stdc++.h>

using namespace std;

const int B1 = 77777;
const int B2 = 12345;

const int md1 = 1e9 + 7;
const int md2 = 1e9 + 9;

int add(int a, int b, int md) {
  return a + b < md ? a + b : a + b - md;
}

void ckadd(int& a, int b, int md) {
  a = add(a, b, md);
}

int mul(int a, int b, int md) {
  return a * 1LL * b % md;
}

void ckmul(int& a, int b, int md) {
  a = mul(a, b, md);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  map<string, int> mp;
  vector<vector<int>> dp(n + 1, vector<int>(k));
  for (int i = 1; i <= n; i++) {
    vector<string> s(k);
    for (int j = 0; j < k; j++) {
      cin >> s[j];
      if (i == 1) {
        dp[i][j] = 1;
      }
    }
    for (int j = 0; j < k; j++) {
      vector<string> prv;
      {
        string t = "";
        for (int p = 0; p + 1 < i; p++) {
          t += s[j][p];
        }
        prv.push_back(t);
      }
      {
        string t = "";
        for (int p = 1; p < i; p++) {
          t += s[j][p];
        }
        prv.push_back(t);
      }
      if ((int) prv.size() >= 2 && prv[0] == prv[1]) {
        prv.pop_back();
      }
      for (string t : prv) {
        ckadd(dp[i][j], mp[t], md1);
      }
    }
    mp.clear();
    for (int j = 0; j < k; j++) {
      ckadd(mp[s[j]], dp[i][j], md1);
    }
  }
  int res = 0;
  for (int i = 0; i < k; i++) {
    ckadd(res, dp[n][i], md1);
  }
  cout << res << '\n';
  return 0;
}

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 5 ms 600 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 3 ms 604 KB Output is correct

Subtask #3
55.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 5 ms 600 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 7 ms 348 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 82 ms 3156 KB Output is correct
13 Correct 81 ms 3168 KB Output is correct
14 Correct 79 ms 3156 KB Output is correct
15 Correct 78 ms 3168 KB Output is correct
16 Correct 30 ms 2760 KB Output is correct
17 Correct 71 ms 3156 KB Output is correct
18 Correct 74 ms 2996 KB Output is correct
19 Correct 71 ms 3084 KB Output is correct
20 Correct 69 ms 3152 KB Output is correct
21 Correct 64 ms 3156 KB Output is correct
22 Correct 30 ms 2644 KB Output is correct