Submission #524595

#	Time	Username	Problem	Language	Result	Execution time	Memory
524595		tato	Trener (COCI20_trener)	C++14	55 / 110	2012 ms	11036 KiB

trener

#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 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 55