Submission #456260

#	Time	Username	Problem	Language	Result	Execution time	Memory
456260		grt	Trener (COCI20_trener)	C++17	110 / 110	91 ms	2500 KiB

trener

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int mod = 1e9 + 7, p = 31;
int n, k;
map<int,int>opt, opt2;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < k; ++j) {
			string s;
			cin >> s;
			int h = 0;
			int h2 = 0;
			int h3 = 0;
			for(auto c : s) {
				h2 = h;
				if(h != 0) {
					h3 = ((ll)h3 * p + (c - 'a' + 1)) % mod;
				}
				h = ((ll)h * p + (c - 'a' + 1)) % mod;
			}
			//cout << h << " " << h2 << " " << h3 << "\n";
			if(i == 0) {
				opt2[h]++;
			} else {
				opt2[h] = (opt2[h] + opt[h2]) % mod;
				if(h3 != h2)
				opt2[h] = (opt2[h] + opt[h3]) % mod;
			}
		}
		opt.swap(opt2);
		opt2.clear();
	}
	int ans = 0;
	for(auto it : opt) {
		ans = (ans + it.ND) % mod;
	}	
	cout << ans;	
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55