oj.uz

Submission #667612

# Submission time Handle Problem Language Result Execution time Memory
667612 2022-12-01T19:36:51 Z Koful123 Trener (COCI20_trener) C++17
110 / 110
 444 ms 10572 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const int N = 55,mod = (int) 1e9 + 7;
int pw1[N],pw2[N];

void calc(){
	pw1[0] = pw2[0] = 1;
	for(int i = 1; i < N; i++){
		pw1[i] = (pw1[i - 1] * 31) % mod;
		pw2[i] = (pw2[i - 1] * 37) % mod; 
	} 
}

void solve(){		

	int n,k; 
	cin >> n >> k;
	
	vector<vector<vector<pair<int,int>>>> v(n);
	for(int i = 0; i < n; i++){
		v[i].resize(k);
		for(int j = 0; j < k; j++){
			string s; cin >> s; int a = 0,b = 0;
			for(int q = 0; q < s.size(); q++){
				a = (a + (s[q] - 'a' + 1) * pw1[q]) % mod;
				b = (b + (s[q] - 'a' + 1) * pw2[q]) % mod;
				if(q == s.size() - 2){
					v[i][j].pb({a,b});
				}
			}
			if(!v[i][j].size()) v[i][j].pb({37,37});
			v[i][j].pb({a,b}); a = 0,b = 0;
			for(int q = 1; q < s.size(); q++){
				a = (a + (s[q] - 'a' + 1) * pw1[q-1]) % mod;
				b = (b + (s[q] - 'a' + 1) * pw2[q-1]) % mod;	
			}
			v[i][j].pb({a,b});
		}
	}		


	vector<vector<int>> dp(n,vector<int>(k));
	for(int i = 0; i < k; i++){
		dp[n - 1][i] = 1;
	}

	for(int i = n - 1; i > 0; i--){
		for(int q = 0; q < k; q++){
			for(int j = 0; j < k; j++){
				if(v[i - 1][j][1] == v[i][q][0] || v[i - 1][j][1] == v[i][q][2]){
					dp[i - 1][j] = (dp[i - 1][j] + dp[i][q]) % mod;
				}
			}
		}
	}	

	int ans = 0;
	for(int i = 0; i < k; i++){
		ans = (ans + dp[0][i]) % mod;
	}

	cout << ans << endl;
}	
 
signed main(){	
 	
 	calc();

	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t = 1;
//	cin >> t;
 
	while(t--)
		solve();
 
	return 0;
}

Compilation message

trener.cpp: In function 'void solve()':
trener.cpp:32:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for(int q = 0; q < s.size(); q++){
      |                   ~~^~~~~~~~~~
trener.cpp:35:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if(q == s.size() - 2){
      |        ~~^~~~~~~~~~~~~~~
trener.cpp:41:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for(int q = 1; q < s.size(); q++){
      |                   ~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 972 KB Output is correct
2 Correct 3 ms 936 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 5 ms 980 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 7 ms 980 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 3 ms 936 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 5 ms 980 KB Output is correct
9 Correct 4 ms 980 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 7 ms 980 KB Output is correct
12 Correct 163 ms 10456 KB Output is correct
13 Correct 162 ms 10484 KB Output is correct
14 Correct 164 ms 10484 KB Output is correct
15 Correct 164 ms 10492 KB Output is correct
16 Correct 444 ms 10572 KB Output is correct
17 Correct 184 ms 10488 KB Output is correct
18 Correct 185 ms 10412 KB Output is correct
19 Correct 184 ms 10444 KB Output is correct
20 Correct 182 ms 10456 KB Output is correct
21 Correct 181 ms 10428 KB Output is correct
22 Correct 412 ms 10488 KB Output is correct