Submission #238714

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238714	2020-06-12T12:19:25 Z	Borbi	Trener (COCI20_trener)	C++14	110 / 110	1215 ms	128376 KB

trener

#include <bits/stdc++.h>

using namespace std;

const int MAXK = 1505;
const int MAXN = 55;

int n, k;
vector <string> v[MAXN];
unordered_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 sr[MAXN][MAXK][MAXK];

const int MOD = 1e9 + 7;

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

int T[MAXN][MAXK];

int rec(int i, int j)
{
	if(i == n - 1) return 1;
	if(T[i][j] != -1) return T[i][j];
	int ans = 0;
	for(int z = 0; z < k; z++)
	{
		if(sr[i][j][z])
		{
			ans = add(ans, rec(i + 1, z));
		}
	}
	return T[i][j] = 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;
			}
		}
	}
	memset(T, -1, sizeof(T));
	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.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	768 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	6 ms	768 KB	Output is correct
4	Correct	5 ms	768 KB	Output is correct

Subtask #2

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	9472 KB	Output is correct
2	Correct	14 ms	9472 KB	Output is correct
3	Correct	14 ms	9472 KB	Output is correct
4	Correct	15 ms	8576 KB	Output is correct
5	Correct	14 ms	9344 KB	Output is correct
6	Correct	16 ms	9344 KB	Output is correct
7	Correct	16 ms	8576 KB	Output is correct

Subtask #3

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	768 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	6 ms	768 KB	Output is correct
4	Correct	5 ms	768 KB	Output is correct
5	Correct	14 ms	9472 KB	Output is correct
6	Correct	14 ms	9472 KB	Output is correct
7	Correct	14 ms	9472 KB	Output is correct
8	Correct	15 ms	8576 KB	Output is correct
9	Correct	14 ms	9344 KB	Output is correct
10	Correct	16 ms	9344 KB	Output is correct
11	Correct	16 ms	8576 KB	Output is correct
12	Correct	255 ms	128376 KB	Output is correct
13	Correct	258 ms	128248 KB	Output is correct
14	Correct	252 ms	128248 KB	Output is correct
15	Correct	252 ms	128376 KB	Output is correct
16	Correct	1201 ms	115064 KB	Output is correct
17	Correct	277 ms	126584 KB	Output is correct
18	Correct	284 ms	126712 KB	Output is correct
19	Correct	287 ms	126712 KB	Output is correct
20	Correct	284 ms	126840 KB	Output is correct
21	Correct	284 ms	126712 KB	Output is correct
22	Correct	1215 ms	115192 KB	Output is correct