Submission #524600

#	Time	Username	Problem	Language	Result	Execution time	Memory
524600		tato	Trener (COCI20_trener)	C++14	55 / 110	2070 ms	9220 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)
{
	int ind1 = 0, ind = 0;

	int ss = s.size();
	for(int i = 0; i < ss; i++)
		if(s[i] != l[i + 1])
			{
				ind = 1;
				break;
			}
	for(int i = 0; i < ss; i++)
		if(s[i] != l[i])
			{
				ind1 = 1;
				break;
			}
	
	if(ind == 1 and ind1 == 1)
		return false;
	else
		return true;
}
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++)
			if(used[m][i] == 1)
			for(int j = 0; j < k; j++)
				{
					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