oj.uz

Submission #524597

# Submission time Handle Problem Language Result Execution time Memory
524597 2022-02-09T15:33:18 Z tato Trener (COCI20_trener) C++14
55 / 110
 2000 ms 9292 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

int n,k;
vector <string> v[51];
ll g[51][1501],used[51][1501];
vector <int> gd[51][1501];
ll p = 1e9+7;
bool check(string s, string l)
{
	int ind1 = 0, ind = 0;

	int ss = s.size();
	for(int i = 0; i < ss; i++)
		if(s[i] != l[i + 1])
			{
				ind = 1;
				break;
			}
	for(int i = 0; i < ss; i++)
		if(s[i] != l[i])
			{
				ind1 = 1;
				break;
			}
	
	if(ind == 1 and ind1 == 1)
		return false;
	else
		return true;
}
void answer()
{
	
	string s;
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= k; j++)
			{
				cin >> s;
				v[i].pb(s);
			}
	for(int i = 0; i < k; i++)
		used[1][i] = 1;
		
	for(int m = 1 ; m < n; m++)
		for(int i = 0; i < k; i++)
			for(int j = 0; j < k; j++)
				{
					if(used[m][i] == 1)
					if(check(v[m][i], v[m+1][j]))
						{
							gd[m][i].pb(j);
							used[m+1][j] = 1;
						}
				}
	
	for(int i = 0; i < k; i++)
	if(used[n][i] == 1)
		g[n][i] = 1;
		
	for(int m = n - 1; m > 0; m--)
		for(int i = 0; i < k; i++)
			if(used[m][i] == 1)
			for(int j  : gd[m][i] )
				if(g[m + 1][j] != 0 )
					g[m][i] = (g[m][i] + g[m + 1][j]) % p;
					
	ll pas = 0;
	
				
	for(int i = 0; i < k; i++)
		pas = (pas + g[1][i]) % p;
		
	cout << pas;
}

int main()
{
	int t = 1;
	
	//cin >> t;
	
	while(t--)
		answer();
	
	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2984 KB Output is correct
2 Correct 27 ms 2968 KB Output is correct
3 Correct 27 ms 2988 KB Output is correct
4 Correct 54 ms 5352 KB Output is correct
5 Correct 37 ms 3136 KB Output is correct
6 Correct 38 ms 3092 KB Output is correct
7 Correct 62 ms 5360 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2124 KB Output is correct
2 Correct 1 ms 2124 KB Output is correct
3 Correct 1 ms 2124 KB Output is correct
4 Correct 1 ms 2124 KB Output is correct
5 Correct 26 ms 2984 KB Output is correct
6 Correct 27 ms 2968 KB Output is correct
7 Correct 27 ms 2988 KB Output is correct
8 Correct 54 ms 5352 KB Output is correct
9 Correct 37 ms 3136 KB Output is correct
10 Correct 38 ms 3092 KB Output is correct
11 Correct 62 ms 5360 KB Output is correct
12 Execution timed out 2060 ms 9292 KB Time limit exceeded
13 Halted 0 ms 0 KB -