답안 #570638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
570638	2022-05-30T20:21:21 Z	NekoRolly	Trener (COCI20_trener)	C++17	110 / 110	240 ms	18436 KB

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.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct

Subtask #2

33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	1364 KB	Output is correct
2	Correct	10 ms	1480 KB	Output is correct
3	Correct	11 ms	1492 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	10 ms	1236 KB	Output is correct
6	Correct	9 ms	1236 KB	Output is correct
7	Correct	2 ms	464 KB	Output is correct

Subtask #3

55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	10 ms	1364 KB	Output is correct
6	Correct	10 ms	1480 KB	Output is correct
7	Correct	11 ms	1492 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	10 ms	1236 KB	Output is correct
10	Correct	9 ms	1236 KB	Output is correct
11	Correct	2 ms	464 KB	Output is correct
12	Correct	240 ms	18436 KB	Output is correct
13	Correct	220 ms	18280 KB	Output is correct
14	Correct	215 ms	18064 KB	Output is correct
15	Correct	231 ms	18124 KB	Output is correct
16	Correct	16 ms	2216 KB	Output is correct
17	Correct	178 ms	14064 KB	Output is correct
18	Correct	189 ms	14212 KB	Output is correct
19	Correct	188 ms	14128 KB	Output is correct
20	Correct	185 ms	14140 KB	Output is correct
21	Correct	183 ms	14452 KB	Output is correct
22	Correct	17 ms	2224 KB	Output is correct