oj.uz

Submission #238709

# Submission time Handle Problem Language Result Execution time Memory
238709 2020-06-12T12:12:02 Z Borbi Trener (COCI20_trener) C++14
22 / 110
 2000 ms 2560 KB 
#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.0 / 22.0

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

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 2560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Execution timed out 2080 ms 2560 KB Time limit exceeded
6 Halted 0 ms 0 KB -