oj.uz

Submission #524600

# Submission time Handle Problem Language Result Execution time Memory
524600 2022-02-09T15:37:52 Z tato Trener (COCI20_trener) C++14
55 / 110
 2000 ms 9220 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++)
			if(used[m][i] == 1)
			for(int j = 0; j < k; j++)
				{
					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 2 ms 2096 KB Output is correct
2 Correct 2 ms 2096 KB Output is correct
3 Correct 1 ms 2096 KB Output is correct
4 Correct 2 ms 2080 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3120 KB Output is correct
2 Correct 31 ms 3100 KB Output is correct
3 Correct 29 ms 3064 KB Output is correct
4 Correct 64 ms 5596 KB Output is correct
5 Correct 43 ms 3180 KB Output is correct
6 Correct 43 ms 3272 KB Output is correct
7 Correct 58 ms 5532 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2096 KB Output is correct
2 Correct 2 ms 2096 KB Output is correct
3 Correct 1 ms 2096 KB Output is correct
4 Correct 2 ms 2080 KB Output is correct
5 Correct 31 ms 3120 KB Output is correct
6 Correct 31 ms 3100 KB Output is correct
7 Correct 29 ms 3064 KB Output is correct
8 Correct 64 ms 5596 KB Output is correct
9 Correct 43 ms 3180 KB Output is correct
10 Correct 43 ms 3272 KB Output is correct
11 Correct 58 ms 5532 KB Output is correct
12 Execution timed out 2070 ms 9220 KB Time limit exceeded
13 Halted 0 ms 0 KB -