Submission #845507

#	Time	Username	Problem	Language	Result	Execution time	Memory
845507		vjudge1	Trener (COCI20_trener)	C++17	55 / 110	1797 ms	524288 KiB

trener

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int32_t main(){
	int n,k;
	cin>>n>>k;
	vector<vector<int>> dp(n,vector<int>(k,0));
	vector<vector<string>> _arr(n,vector<string>(k));
	for (int i = 0; i < n; i++){
		for (int j = 0; j < k; j++){
			cin>>_arr[i][j];
		}
	}
	vector<vector<vector<int>>> arr(n-1,vector<vector<int>>(k));
	map<string,vector<int>> mp;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < k; j++){
			mp[_arr[i][j]].push_back(j);
		}
	}
	for (int i = 0; i < n-1; i++){
		for (int j = 0; j < k; j++){
			string str = _arr[i][j];
			set<string> needless;
			for (char chr = 'a'; chr <= 'z'; chr++){
				needless.insert(str+chr);
				needless.insert(chr+str);
			}
			for (auto it : needless){
				if (mp.count(it)){
					for (auto it2 : mp[it]){
						arr[i][j].push_back(it2);
					}
				}
			}
		}
	}
	for (int node = n-1; node >= 0; node--){
		for (int flag = 0; flag < k; flag++){
			if (node==n-1){
				dp[node][flag]=1;
				continue;
			}
			for (int i = 0; i < arr[node][flag].size(); i++){
				dp[node][flag]+=dp[node+1][arr[node][flag][i]];
				dp[node][flag]%=MOD;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < k; i++){
		ans+=dp[0][i];
		ans%=MOD;
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

trener.cpp: In function 'int32_t main()':
trener.cpp:45:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (int i = 0; i < arr[node][flag].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 55