oj.uz

Submission #291800

# Submission time Handle Problem Language Result Execution time Memory
291800 2020-09-05T19:23:58 Z penguinhacker Trener (COCI20_trener) C++17
110 / 110
 130 ms 7684 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int MOD=1e9+7, M[2]={(int)1e9+9, (int)1e9+7}, P[2]={37, 41};
ar<int, 2> getHash(string s) {
	ar<int, 2> res;
	for (int i=0; i<2; ++i) {
		ll pp=1, hsh=0;
		for (char c : s) {
			hsh=(hsh+(c-'a'+1)*pp)%M[i];
			pp=pp*P[i]%MOD;
		}
		res[i]=hsh;
	}
	return res;
}

int n, k;
string name[50][1500];
map<ar<int, 2>, int> dp, last;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	for (int i=0; i<n; ++i) for (int j=0; j<k; ++j) cin >> name[i][j];
	for (int i=0; i<k; ++i) ++dp[getHash(name[0][i])];
	for (int i=1; i<n; ++i) { //current string is of length i+1
		swap(dp, last);
		dp.clear();
		for (int j=0; j<k; ++j) {
			ar<int, 2> cur=getHash(name[i][j]);
			ar<int, 2> hsh=getHash(name[i][j].substr(0, i));
			auto it=last.find(hsh);
			if (it!=last.end()) dp[cur]=(dp[cur]+it->second)%MOD;
			ar<int, 2> hsh2=getHash(name[i][j].substr(1));
			if (hsh!=hsh2) {
				hsh=hsh2;
				it=last.find(hsh);
				if (it!=last.end()) dp[cur]=(dp[cur]+it->second)%MOD;
			}
		}
		//for (auto& x : dp) {cout << x.first << " " << x.second << "\n";}
		//for (auto& x : dp) if (x.second>=MOD) x.second-=MOD;
		//cout << "\n\n";
	}
	int ans=0;
	for (auto& x : dp) ans=(ans+x.second)%MOD;
	cout << ans << "\n";
	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3072 KB Output is correct
2 Correct 10 ms 3200 KB Output is correct
3 Correct 10 ms 3072 KB Output is correct
4 Correct 8 ms 2944 KB Output is correct
5 Correct 9 ms 2944 KB Output is correct
6 Correct 9 ms 3072 KB Output is correct
7 Correct 8 ms 2944 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2720 KB Output is correct
5 Correct 11 ms 3072 KB Output is correct
6 Correct 10 ms 3200 KB Output is correct
7 Correct 10 ms 3072 KB Output is correct
8 Correct 8 ms 2944 KB Output is correct
9 Correct 9 ms 2944 KB Output is correct
10 Correct 9 ms 3072 KB Output is correct
11 Correct 8 ms 2944 KB Output is correct
12 Correct 126 ms 7608 KB Output is correct
13 Correct 130 ms 7672 KB Output is correct
14 Correct 124 ms 7612 KB Output is correct
15 Correct 127 ms 7552 KB Output is correct
16 Correct 91 ms 7448 KB Output is correct
17 Correct 121 ms 7544 KB Output is correct
18 Correct 121 ms 7544 KB Output is correct
19 Correct 122 ms 7684 KB Output is correct
20 Correct 120 ms 7544 KB Output is correct
21 Correct 120 ms 7552 KB Output is correct
22 Correct 95 ms 7424 KB Output is correct