Submission #667612

#	Time	Username	Problem	Language	Result	Execution time	Memory
667612		Koful123	Trener (COCI20_trener)	C++17	110 / 110	444 ms	10572 KiB

trener

#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 (stderr)

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