oj.uz

Submission #570637

# Submission time Handle Problem Language Result Execution time Memory
570637 2022-05-30T20:17:45 Z NekoRolly Trener (COCI20_trener) C++17
0 / 110
 11 ms 1492 KB 
#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 { 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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -