oj.uz

Submission #845231

# Submission time Handle Problem Language Result Execution time Memory
845231 2023-09-06T12:42:30 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 26704 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++){
			vector < int > ind1 = mpa[string(v[i][j].begin() , v[i][j].end()-1)];
			vector < int > ind2 = mpa[string(v[i][j].begin()+1 , v[i][j].end())];
			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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2136 KB Output is correct
2 Correct 6 ms 2140 KB Output is correct
3 Correct 6 ms 2140 KB Output is correct
4 Correct 16 ms 856 KB Output is correct
5 Correct 5 ms 1624 KB Output is correct
6 Correct 5 ms 1624 KB Output is correct
7 Correct 16 ms 856 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 2136 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 6 ms 2140 KB Output is correct
8 Correct 16 ms 856 KB Output is correct
9 Correct 5 ms 1624 KB Output is correct
10 Correct 5 ms 1624 KB Output is correct
11 Correct 16 ms 856 KB Output is correct
12 Correct 151 ms 26448 KB Output is correct
13 Correct 157 ms 26448 KB Output is correct
14 Correct 153 ms 26448 KB Output is correct
15 Correct 149 ms 26704 KB Output is correct
16 Execution timed out 2037 ms 7000 KB Time limit exceeded
17 Halted 0 ms 0 KB -