oj.uz

Submission #845491

# Submission time Handle Problem Language Result Execution time Memory
845491 2023-09-06T13:51:43 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 23428 KB 
#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

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.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 1628 KB Output is correct
2 Correct 83 ms 1800 KB Output is correct
3 Correct 89 ms 2280 KB Output is correct
4 Correct 63 ms 5928 KB Output is correct
5 Correct 66 ms 1816 KB Output is correct
6 Correct 68 ms 1828 KB Output is correct
7 Correct 64 ms 5732 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 82 ms 1628 KB Output is correct
6 Correct 83 ms 1800 KB Output is correct
7 Correct 89 ms 2280 KB Output is correct
8 Correct 63 ms 5928 KB Output is correct
9 Correct 66 ms 1816 KB Output is correct
10 Correct 68 ms 1828 KB Output is correct
11 Correct 64 ms 5732 KB Output is correct
12 Execution timed out 2088 ms 23428 KB Time limit exceeded
13 Halted 0 ms 0 KB -