oj.uz

Submission #845507

# Submission time Handle Problem Language Result Execution time Memory
845507 2023-09-06T13:56:04 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 1797 ms 524288 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,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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 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 79 ms 1624 KB Output is correct
2 Correct 83 ms 2124 KB Output is correct
3 Correct 82 ms 1624 KB Output is correct
4 Correct 59 ms 5968 KB Output is correct
5 Correct 67 ms 1872 KB Output is correct
6 Correct 67 ms 1872 KB Output is correct
7 Correct 60 ms 5968 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 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 79 ms 1624 KB Output is correct
6 Correct 83 ms 2124 KB Output is correct
7 Correct 82 ms 1624 KB Output is correct
8 Correct 59 ms 5968 KB Output is correct
9 Correct 67 ms 1872 KB Output is correct
10 Correct 67 ms 1872 KB Output is correct
11 Correct 60 ms 5968 KB Output is correct
12 Correct 1724 ms 23432 KB Output is correct
13 Correct 1797 ms 23420 KB Output is correct
14 Correct 1740 ms 23320 KB Output is correct
15 Correct 1704 ms 23608 KB Output is correct
16 Runtime error 710 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -