oj.uz

Submission #1006377

# Submission time Handle Problem Language Result Execution time Memory
1006377 2024-06-23T22:48:41 Z MilosMilutinovic Trener (COCI20_trener) C++14
22 / 110
 640 ms 2388 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<pair<int, int>, 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++) {
      map<pair<int, int>, bool> was;
      for (int l = 0; l < i; l++) {
        int pw1 = 1;
        int pw2 = 1;
        int hs1 = 0;
        int hs2 = 0;
        for (int r = l; r < i; r++) {
          int v = (int) (s[j][r] - 'a' + 1);
          ckadd(hs1, mul(v, pw1, md1), md1);
          ckadd(hs2, mul(v, pw1, md1), md1);
          if (!was[{hs1, hs2}]) {
            ckadd(dp[i][j], mp[{hs1, hs2}], md1);
            was[{hs1, hs2}] = true;
          }
          ckmul(pw1, B1, md1);
          ckmul(pw2, B2, md2);
        }
      }
    }
    mp.clear();
    for (int j = 0; j < k; j++) {
      int pw1 = 1;
      int pw2 = 1;
      int hs1 = 0;
      int hs2 = 0;
      for (int p = 0; p < i; p++) {
        int v = (int) (s[j][p] - 'a' + 1);
        ckadd(hs1, mul(v, pw1, md1), md1);
        ckadd(hs2, mul(v, pw1, md1), md1);
        ckmul(pw1, B1, md1);
        ckmul(pw2, B2, md2);
      }
      ckadd(mp[{hs1, hs2}], 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 1 ms 480 KB Output is correct
2 Correct 1 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
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 2388 KB Output is correct
2 Correct 582 ms 1876 KB Output is correct
3 Correct 640 ms 2388 KB Output is correct
4 Correct 23 ms 464 KB Output is correct
5 Correct 500 ms 1592 KB Output is correct
6 Incorrect 506 ms 1580 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 480 KB Output is correct
2 Correct 1 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 640 ms 2388 KB Output is correct
6 Correct 582 ms 1876 KB Output is correct
7 Correct 640 ms 2388 KB Output is correct
8 Correct 23 ms 464 KB Output is correct
9 Correct 500 ms 1592 KB Output is correct
10 Incorrect 506 ms 1580 KB Output isn't correct
11 Halted 0 ms 0 KB -