Submission #570638

#	Time	Username	Problem	Language	Result	Execution time	Memory
570638		NekoRolly	Trener (COCI20_trener)	C++17	110 / 110	240 ms	18436 KiB

trener

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3+4;
const int mod = 1e9+7;

map<string,int> cnt,dp;
int n,k,ans;

int P(int a,int b){ return 1ll*a*b%mod;}

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

	cin >> n >> k;

	for (int i=1; i<=n; i++) for (int j=0; j<k; j++){
		string s,t1,t2; cin >> s;
		if (i == 1) dp[s] = 1;
		else if (!dp.count(s)){ t1 = s.substr(0, i-1), t2 = s.substr(1, i-1);
			if (dp.count(t1)) dp[s] = (dp[s] + P(dp[t1], cnt[t1]))%mod;
			if (t1 != t2 && dp.count(t2)) dp[s] = (dp[s] + P(dp[t2], cnt[t2]))%mod;
		}
		cnt[s]++;
		if (i == n) ans = (ans + dp[s])%mod;
	}

	cout << ans << "\n";

    return 0;
}

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