Submission #238715

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238715	2020-06-12T12:20:29 Z	Borbi	Trener (COCI20_trener)	C++14	110 / 110	1195 ms	129656 KB

trener

#include <bits/stdc++.h>

using namespace std;

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

int n, k;
string v[MAXN][MAXK];
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][j] = 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	6 ms	3328 KB	Output is correct
2	Correct	6 ms	3328 KB	Output is correct
3	Correct	6 ms	3328 KB	Output is correct
4	Correct	7 ms	3328 KB	Output is correct

Subtask #2

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	11904 KB	Output is correct
2	Correct	18 ms	11904 KB	Output is correct
3	Correct	18 ms	11904 KB	Output is correct
4	Correct	16 ms	11008 KB	Output is correct
5	Correct	18 ms	11776 KB	Output is correct
6	Correct	17 ms	11776 KB	Output is correct
7	Correct	17 ms	11008 KB	Output is correct

Subtask #3

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	3328 KB	Output is correct
2	Correct	6 ms	3328 KB	Output is correct
3	Correct	6 ms	3328 KB	Output is correct
4	Correct	7 ms	3328 KB	Output is correct
5	Correct	17 ms	11904 KB	Output is correct
6	Correct	18 ms	11904 KB	Output is correct
7	Correct	18 ms	11904 KB	Output is correct
8	Correct	16 ms	11008 KB	Output is correct
9	Correct	18 ms	11776 KB	Output is correct
10	Correct	17 ms	11776 KB	Output is correct
11	Correct	17 ms	11008 KB	Output is correct
12	Correct	293 ms	129400 KB	Output is correct
13	Correct	292 ms	129656 KB	Output is correct
14	Correct	295 ms	129528 KB	Output is correct
15	Correct	287 ms	129612 KB	Output is correct
16	Correct	1193 ms	115448 KB	Output is correct
17	Correct	360 ms	127224 KB	Output is correct
18	Correct	347 ms	127480 KB	Output is correct
19	Correct	322 ms	127352 KB	Output is correct
20	Correct	328 ms	127480 KB	Output is correct
21	Correct	323 ms	127224 KB	Output is correct
22	Correct	1195 ms	115192 KB	Output is correct