oj.uz

Submission #845412

# Submission time Handle Problem Language Result Execution time Memory
845412 2023-09-06T13:30:59 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 34896 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
struct HASH{
	int sz = 10;
	int p[10] = {29,31,89,59,67,71,31,41,61,71};
	vector < int > get(string &str){
		vector < int > ret(sz,0) , kat(sz,1);
		for(auto itr : str){
			for(int i = 0;i<sz;i++) {
				ret[i] = (ret[i] + kat[i] * (itr - 'a' + 1)) % mod;
				kat[i] = (kat[i] * p[i]) % mod;
			}
		}
		return ret;
	}
} h;
void solve(){
	int n,k;cin >> n >> k;
	string v[n+1][k];
	map < vector < int > , vector < int > > mpa;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<k;j++){
			cin >> v[i][j];
			mpa[h.get(v[i][j])].push_back(j);
		}
	}
	int dp[n+1][k];
	memset(dp , 0 , sizeof(dp));
	for(int i = 0;i<k;i++)dp[1][i] = 1;
	for(int i = 2;i<=n;i++){
		for(int j = 0;j<k;j++){
			string s1 = string(v[i][j].begin() , v[i][j].end()-1) , s2 = string(v[i][j].begin()+1 , v[i][j].end());
			vector < int > ind1 = mpa[h.get(s1)];
			vector < int > ind2 = mpa[h.get(s2)];
			for(auto itr : ind2)ind1.push_back(itr);
			sort(ind1.begin(),ind1.end());
			ind1.resize(unique(ind1.begin() , ind1.end()) - ind1.begin());
			for(auto itr : ind1){
				dp[i][j] = (dp[i][j] + dp[i-1][itr]) % mod;
			}
		}
	}
	int ans = 0;
	for(int i = 0;i<k;i++)ans = (ans + dp[n][i]) % mod;
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2652 KB Output is correct
2 Correct 17 ms 2652 KB Output is correct
3 Correct 22 ms 2652 KB Output is correct
4 Correct 26 ms 860 KB Output is correct
5 Correct 16 ms 2140 KB Output is correct
6 Correct 15 ms 2188 KB Output is correct
7 Correct 25 ms 904 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 23 ms 2652 KB Output is correct
6 Correct 17 ms 2652 KB Output is correct
7 Correct 22 ms 2652 KB Output is correct
8 Correct 26 ms 860 KB Output is correct
9 Correct 16 ms 2140 KB Output is correct
10 Correct 15 ms 2188 KB Output is correct
11 Correct 25 ms 904 KB Output is correct
12 Correct 347 ms 34848 KB Output is correct
13 Correct 356 ms 34644 KB Output is correct
14 Correct 336 ms 34896 KB Output is correct
15 Correct 337 ms 34868 KB Output is correct
16 Execution timed out 2058 ms 6992 KB Time limit exceeded
17 Halted 0 ms 0 KB -