oj.uz

Submission #524595

# Submission time Handle Problem Language Result Execution time Memory
524595 2022-02-09T15:26:49 Z tato Trener (COCI20_trener) C++14
55 / 110
 2000 ms 11036 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

int n,k;
vector <string> v[51];
ll g[51][1501],used[51][1501];
vector <int> gd[51][1501];
ll p = 1e9+7;
bool check(string s, string l)
{
	if(s == l.substr(0,s.size()) or s == l.substr(1))
		return true;
	else
		return false;
	
	
}
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].pb(s);
			}
	for(int i = 0; i < k; i++)
		used[1][i] = 1;
		
	for(int m = 1 ; m < n; m++)
		for(int i = 0; i < k; i++)
			for(int j = 0; j < k; j++)
				{
					if(used[m][i] == 1)
					if(check(v[m][i], v[m+1][j]))
						{
							gd[m][i].pb(j);
							used[m+1][j] = 1;
						}
				}
	
	for(int i = 0; i < k; i++)
	if(used[n][i] == 1)
		g[n][i] = 1;
		
	for(int m = n - 1; m > 0; m--)
		for(int i = 0; i < k; i++)
			if(used[m][i] == 1)
			for(int j  : gd[m][i] )
				if(g[m + 1][j] != 0 )
					g[m][i] = (g[m][i] + g[m + 1][j]) % p;
					
	ll pas = 0;
	
				
	for(int i = 0; i < k; i++)
		pas = (pas + g[1][i]) % 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 1 ms 2116 KB Output is correct
2 Correct 1 ms 2096 KB Output is correct
3 Correct 1 ms 2124 KB Output is correct
4 Correct 2 ms 2100 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3144 KB Output is correct
2 Correct 54 ms 3144 KB Output is correct
3 Correct 47 ms 3080 KB Output is correct
4 Correct 48 ms 5584 KB Output is correct
5 Correct 49 ms 3240 KB Output is correct
6 Correct 51 ms 3240 KB Output is correct
7 Correct 48 ms 5464 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2116 KB Output is correct
2 Correct 1 ms 2096 KB Output is correct
3 Correct 1 ms 2124 KB Output is correct
4 Correct 2 ms 2100 KB Output is correct
5 Correct 48 ms 3144 KB Output is correct
6 Correct 54 ms 3144 KB Output is correct
7 Correct 47 ms 3080 KB Output is correct
8 Correct 48 ms 5584 KB Output is correct
9 Correct 49 ms 3240 KB Output is correct
10 Correct 51 ms 3240 KB Output is correct
11 Correct 48 ms 5464 KB Output is correct
12 Execution timed out 2012 ms 11036 KB Time limit exceeded
13 Halted 0 ms 0 KB -