oj.uz

Submission #238712

# Submission time Handle Problem Language Result Execution time Memory
238712 2020-06-12T12:14:57 Z Borbi Trener (COCI20_trener) C++14
22 / 110
 12 ms 2816 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1505;
const int MAXK = 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 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
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 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Incorrect 12 ms 2816 KB Output isn't correct
6 Halted 0 ms 0 KB -