oj.uz

답안 #845379

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
845379 2023-09-06T13:24:09 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 26564 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
void solve(){
	int n,k;cin >> n >> k;
	string v[n+1][k];
	map < string , vector < int > > mpa;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<k;j++){
			cin >> v[i][j];
			mpa[v[i][j]].push_back(j);
		}
	}
	int dp[n+1][k];
	memset(dp , 0 , sizeof(dp));
	for(int i = 0;i<k;i++)dp[1][i] = 1;
	for(int i = 2;i<=n;i++){
		for(int j = 0;j<k;j++){
			string s1 = string(v[i][j].begin() , v[i][j].end()-1);
			string s2 = string(v[i][j].begin()+1 , v[i][j].end()); 
			vector < int > ind1 = mpa[s1];
			vector < int > ind2 = mpa[s2];
			for(auto itr : ind2)ind1.push_back(itr);
			sort(ind1.begin(),ind1.end());
			ind1.resize(unique(ind1.begin() , ind1.end()) - ind1.begin());
			for(auto itr : ind1){
				dp[i][j] = (dp[i][j] + dp[i-1][itr]) % mod;
			}
		}
	}
	int ans = 0;
	for(int i = 0;i<k;i++)ans = (ans + dp[n][i]) % mod;
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2140 KB Output is correct
2 Correct 8 ms 2140 KB Output is correct
3 Correct 9 ms 2140 KB Output is correct
4 Correct 15 ms 860 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 6 ms 1624 KB Output is correct
7 Correct 15 ms 860 KB Output is correct

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 2140 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 9 ms 2140 KB Output is correct
8 Correct 15 ms 860 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 6 ms 1624 KB Output is correct
11 Correct 15 ms 860 KB Output is correct
12 Correct 156 ms 26564 KB Output is correct
13 Correct 175 ms 26448 KB Output is correct
14 Correct 164 ms 26452 KB Output is correct
15 Correct 153 ms 26512 KB Output is correct
16 Execution timed out 2061 ms 7004 KB Time limit exceeded
17 Halted 0 ms 0 KB -