oj.uz

Submission #845460

# Submission time Handle Problem Language Result Execution time Memory
845460 2023-09-06T13:41:31 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 19456 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
const int mod = 1e9 + 7;
inline long long get1(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}
inline long long get2(string const& s) {
    const int p = 37;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}
inline pair < int , int > get(string const& s){
	return {get1(s),get2(s)};
}
void solve(){
	int n,k;cin >> n >> k;
	string v[n+1][k];
	map < pair < int , int > , vector < int > > mpa;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<k;j++){
			cin >> v[i][j];
			mpa[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[get(s1)];
			vector < int > ind2 = mpa[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 1 ms 344 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 7 ms 1624 KB Output is correct
2 Correct 7 ms 1624 KB Output is correct
3 Correct 8 ms 1624 KB Output is correct
4 Correct 18 ms 856 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 7 ms 1368 KB Output is correct
7 Correct 19 ms 856 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 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 1624 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 8 ms 1624 KB Output is correct
8 Correct 18 ms 856 KB Output is correct
9 Correct 7 ms 1372 KB Output is correct
10 Correct 7 ms 1368 KB Output is correct
11 Correct 19 ms 856 KB Output is correct
12 Correct 186 ms 19456 KB Output is correct
13 Correct 176 ms 19320 KB Output is correct
14 Correct 165 ms 19300 KB Output is correct
15 Correct 161 ms 19284 KB Output is correct
16 Execution timed out 2033 ms 7004 KB Time limit exceeded
17 Halted 0 ms 0 KB -