Submission #238713

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238713	2020-06-12T12:18:27 Z	Borbi	Trener (COCI20_trener)	C++14	110 / 110	1138 ms	130812 KB

trener

#include <bits/stdc++.h>

using namespace std;

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

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 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	640 KB	Output is correct
3	Correct	5 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	16 ms	9600 KB	Output is correct
2	Correct	18 ms	9600 KB	Output is correct
3	Correct	16 ms	9600 KB	Output is correct
4	Correct	15 ms	8704 KB	Output is correct
5	Correct	16 ms	9600 KB	Output is correct
6	Correct	17 ms	9472 KB	Output is correct
7	Correct	15 ms	8704 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	640 KB	Output is correct
3	Correct	5 ms	768 KB	Output is correct
4	Correct	5 ms	768 KB	Output is correct
5	Correct	16 ms	9600 KB	Output is correct
6	Correct	18 ms	9600 KB	Output is correct
7	Correct	16 ms	9600 KB	Output is correct
8	Correct	15 ms	8704 KB	Output is correct
9	Correct	16 ms	9600 KB	Output is correct
10	Correct	17 ms	9472 KB	Output is correct
11	Correct	15 ms	8704 KB	Output is correct
12	Correct	303 ms	130552 KB	Output is correct
13	Correct	310 ms	130680 KB	Output is correct
14	Correct	303 ms	130808 KB	Output is correct
15	Correct	303 ms	130812 KB	Output is correct
16	Correct	1138 ms	116476 KB	Output is correct
17	Correct	336 ms	128376 KB	Output is correct
18	Correct	341 ms	128632 KB	Output is correct
19	Correct	340 ms	128504 KB	Output is correct
20	Correct	340 ms	128608 KB	Output is correct
21	Correct	342 ms	128508 KB	Output is correct
22	Correct	1129 ms	116524 KB	Output is correct