Submission #238709

#	Time	Username	Problem	Language	Result	Execution time	Memory
238709		Borbi	Trener (COCI20_trener)	C++14	22 / 110	2080 ms	2560 KiB

trener

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1.5e3 + 5;

int n, k;
vector <string> v[MAXN];
map <string, vector<int>> str[MAXN];;

void read_input()
{
	cin >> n >> k;
	string s;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < k; j++)
		{
			cin >> s;
			v[i].push_back(s);
			if(i > 0)
			{
				string f = s.substr(0, i);
				str[i][f].push_back(j);
				//cout << f << "\n";
				f = s.substr(1, i + 1);
				str[i][f].push_back(j);
				//cout << f << "\n";
			}
		}
	}
}

bool check(int i, int j, int z)
{
	return false;
}

bool sr[MAXN][51][51];

const int MOD = 1e9 + 7;

int add(int f, int s)
{
	f += s;
	if(f >= MOD) f %= MOD;
	return f;
}

int rec(int i, int j)
{
	if(i == n - 1) return 1;
	int ans = 0;
	for(int z = 0; z < k; z++)
	{
		if(sr[i][j][z])
		{
			ans = add(ans, rec(i + 1, z));
		}
	}
	return ans;
}

void solve()
{
	for(int i = 0; i < n - 1; i++)
	{
		for(int j = 0; j < k; j++)
		{
			for(auto x : str[i + 1][v[i][j]])
			{
				//cout << i << " " << j << " " << x << "\n";
				sr[i][j][x] = true;
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < k; i++)
	{
		ans = add(ans, rec(0, i));
	}
	cout << ans << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	read_input();
	solve();

	return 0;
}

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