oj.uz

Submission #845320

# Submission time Handle Problem Language Result Execution time Memory
845320 2023-09-06T13:09:44 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 25652 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
const int mod = 1e9 + 7;
void solve(){
	int n,k;cin >> n >> k;
	string v[n+1][k];
	unordered_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 1 ms 344 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 4 ms 2136 KB Output is correct
2 Correct 5 ms 2136 KB Output is correct
3 Correct 4 ms 2136 KB Output is correct
4 Correct 18 ms 892 KB Output is correct
5 Correct 5 ms 1624 KB Output is correct
6 Correct 4 ms 1628 KB Output is correct
7 Correct 22 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 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 4 ms 2136 KB Output is correct
6 Correct 5 ms 2136 KB Output is correct
7 Correct 4 ms 2136 KB Output is correct
8 Correct 18 ms 892 KB Output is correct
9 Correct 5 ms 1624 KB Output is correct
10 Correct 4 ms 1628 KB Output is correct
11 Correct 22 ms 856 KB Output is correct
12 Correct 94 ms 25652 KB Output is correct
13 Correct 87 ms 25544 KB Output is correct
14 Correct 107 ms 25536 KB Output is correct
15 Correct 96 ms 25540 KB Output is correct
16 Execution timed out 2057 ms 7004 KB Time limit exceeded
17 Halted 0 ms 0 KB -