Submission #845491

#	Time	Username	Problem	Language	Result	Execution time	Memory
845491		vjudge1	Trener (COCI20_trener)	C++17	55 / 110	2088 ms	23428 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,-1));
	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);
					}
				}
			}
		}
	}
	function<int(int,int)> f;f = [&](int node, int flag)->int{
		if (node==n-1) return 1;
		if (dp[node][flag]!=-1) return dp[node][flag];
		dp[node][flag]=0;
		for (int i = 0; i < arr[node][flag].size(); i++){
			dp[node][flag]+=f(node+1,arr[node][flag][i]);
			dp[node][flag]%=MOD;
		}
		return dp[node][flag];
	};
	int ans = 0;
	for (int i = 0; i < k; i++){
		ans+=f(0,i);
		ans%=MOD;
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

trener.cpp: In lambda function:
trener.cpp:43:21: 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]
   43 |   for (int i = 0; i < arr[node][flag].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~

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