oj.uz

Submission #524523

# Submission time Handle Problem Language Result Execution time Memory
524523 2022-02-09T11:56:18 Z tato Trener (COCI20_trener) C++14
55 / 110
 2000 ms 8224 KB 
#include <bits/stdc++.h>

using namespace std;





long long p = 1e9+7;
map <string, long long > mp;
long long pas = 0;
int n,k;
vector <string > v[51];
long long g[51][1501];
int used[51][1501];
bool check(string s, string l)
{
	
	string t = l.substr(0,l.size() - 1);
	string f = l.substr(1);
	if(s == t or s == f)
		return true;
	else
		return false;
	
}

long long dfs(pair <int,int> par,int m)
{
	if(m == n + 1)
		return 1;
	if(used[par.first][par.second] == 1)
		return g[par.first][par.second];
	used[par.first][par.second] = 1;
	for(int i = 0; i < k; i++)
	if(check(v[par.first][par.second], v[m][i]))
		{
			long long cnt = dfs({m,i}, m + 1);
			g[par.first][par.second] = (g[par.first][par.second] + cnt) % p;
		}
			
	return  g[par.first][par.second];

	
}

void answer()
{

	string s;
	cin >> n >> k;
	

	
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= k; j++)
			{
				cin >> s;
				v[i].push_back(s);
			}
	for (int i = 0; i < k; i++)
		pas = (dfs({1,i},2) + pas) % p;
	
	cout << pas;
	
	
}


int main()
{
	int t = 1;
	//cin >> t;
	
	while(t--)
		answer();
	
	
	
	
	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1112 KB Output is correct
2 Correct 48 ms 1124 KB Output is correct
3 Correct 50 ms 1116 KB Output is correct
4 Correct 54 ms 1080 KB Output is correct
5 Correct 49 ms 1168 KB Output is correct
6 Correct 65 ms 1336 KB Output is correct
7 Correct 54 ms 1220 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 49 ms 1112 KB Output is correct
6 Correct 48 ms 1124 KB Output is correct
7 Correct 50 ms 1116 KB Output is correct
8 Correct 54 ms 1080 KB Output is correct
9 Correct 49 ms 1168 KB Output is correct
10 Correct 65 ms 1336 KB Output is correct
11 Correct 54 ms 1220 KB Output is correct
12 Execution timed out 2008 ms 8224 KB Time limit exceeded
13 Halted 0 ms 0 KB -