oj.uz

Submission #998997

# Submission time Handle Problem Language Result Execution time Memory
998997 2024-06-15T03:53:32 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 772 ms 8688 KB 
#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9+7, base = 727;

int main()
{
  int n, k;
  cin >> n >> k;
  string s[n][k];
  int hsh[n][k];

  for(int i = 0; i < n; i ++)
    for(int j = 0; j < k; j++)
      cin >> s[i][j];

  int dp[n][k];

  for(int i = 0; i < k; i++)
    dp[0][i] = 1;

  for(int i = 0; i < k ; i++)
    hsh[0][i] = s[0][i][0] % mod;
  
  
  for(int i = 1; i < n; i ++)
    {
      for(int j = 0; j < k; j++)
	{
	  dp[i][j] = 0;
	  int hshp = 0, hshs = 0, hshc = 0;

	  for(int l = 0; l < s[i][j].size(); l++)
	    hshc = (1ll * hshc * base % mod + s[i][j][l]) % mod;

	  for(int l = 0; l + 1 < s[i][j].size(); l++)
	    hshp = (1ll * hshp * base % mod + s[i][j][l]) % mod;

	  for(int l = 1; l < s[i][j].size(); l++)
	    hshs = (1ll * hshs * base % mod + s[i][j][l]) % mod;

	  hsh[i][j] = hshc;
	  for(int l = 0; l < k; l++)
	    if(hsh[i - 1][l] == hshp || hsh[i - 1][l] == hshs)
	      dp[i][j] = (dp[i][j] + dp[i - 1][l]) % mod;
	    
	  // cerr << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
	}
    }

  int ans = 0;
  for(int i = 0; i < k; i ++)
    ans = (ans + dp[n - 1][i]) % mod;
  cout << ans << endl;
  
  return 0;
}

Compilation message

trener.cpp: In function 'int main()':
trener.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for(int l = 0; l < s[i][j].size(); l++)
      |                   ~~^~~~~~~~~~~~~~~~
trener.cpp:37:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(int l = 0; l + 1 < s[i][j].size(); l++)
      |                   ~~~~~~^~~~~~~~~~~~~~~~
trener.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for(int l = 1; l < s[i][j].size(); l++)
      |                   ~~^~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 860 KB Output is correct
2 Correct 6 ms 860 KB Output is correct
3 Correct 6 ms 860 KB Output is correct
4 Correct 9 ms 860 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 9 ms 860 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 7 ms 860 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 9 ms 860 KB Output is correct
9 Correct 6 ms 860 KB Output is correct
10 Correct 6 ms 860 KB Output is correct
11 Correct 9 ms 860 KB Output is correct
12 Correct 156 ms 8544 KB Output is correct
13 Correct 151 ms 8528 KB Output is correct
14 Correct 156 ms 8688 KB Output is correct
15 Correct 155 ms 8532 KB Output is correct
16 Correct 759 ms 8684 KB Output is correct
17 Correct 175 ms 8456 KB Output is correct
18 Correct 174 ms 8528 KB Output is correct
19 Correct 178 ms 8484 KB Output is correct
20 Correct 172 ms 8528 KB Output is correct
21 Correct 171 ms 8528 KB Output is correct
22 Correct 772 ms 8580 KB Output is correct