Submission #1006378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006378		MilosMilutinovic	Trener (COCI20_trener)	C++14	110 / 110	82 ms	3168 KiB

trener

#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 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55