Submission #524609

#	Time	Username	Problem	Language	Result	Execution time	Memory
524609		tato	Trener (COCI20_trener)	C++14	0 / 110	36 ms	5968 KiB

trener

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

int n,k;
vector <string> v[51];
map <string,int> used;
set <string>  gd[51][1501];
ll p = 1e9+7;
map <string, ll> g;

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[v[1][i]] = 1;
		
	for(int m = 1 ; m < n; m++)
		for(int i = 0; i < k; i++)
			if(used[v[m][i]] == 1)
			for(int j = 0; j < k; j++)
				{
					if(check(v[m][i], v[m+1][j]))
						{
							gd[m][i].insert(v[m+1][j]);
							used[v[m+1][j]] = 1;
						}
				}
	
	for(int i = 0; i < k; i++)
	if(used[v[n][i]] == 1)
		g[v[n][i]] = 1;
		
	for(int m = n - 1; m > 0; m--)
		for(int i = 0; i < k; i++)
			if(used[v[m][i]] == 1)
			for(auto it = gd[m][i].begin(); it != gd[m][i].end(); it++ )
				if(g[*it] != 0 )
					g[v[m][i]] = (g[v[m][i]] + g[*it]) % p;
					
	ll pas = 0;
	
				
	for(int i = 0; i < k; i++)
		pas = (pas + g[v[1][i]]) % p;
		
	cout << pas;
}

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

• Subtask 1: 0 / 22
• Subtask 2: 0 / 33
• Subtask 3: 0 / 55