oj.uz

Submission #373088

# Submission time Handle Problem Language Result Execution time Memory
373088 2021-03-03T09:23:35 Z Nimbostratus Trener (COCI20_trener) C++17
110 / 110
 864 ms 40772 KB 
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define pb push_back
#define ppb pop_back
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define cln(a,s) memset((a),0,sizeof((a)[0])*(s))
#define all(x) (x).begin() , (x).end()
#define fi first
#define se second
#define int long long
using pii = pair<int,int>;
using ll = long long;
const int maxn = 55;
const int maxk = 1505;
const int inf = 1e9;
const int mod = 1e9+7;
const int hmod = 1e9+9;

int n,k;
string a[maxn][maxk];
int dp[maxn][maxk],hsh[maxn][maxk][maxn];
//a[i][j] 1 indexli
//stringler 0 indexli
//dp 1 indexli
//hsh[][] 1 indexli , stringler 0 indexli olduğu için hsh[][] 0 indexli

int32_t main () {
	//freopen("in","r",stdin); freopen("out","w",stdout);
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	cin >> n >> k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++) {
			cin >> a[i][j];
			string tmp = a[i][j];
			hsh[i][j][0] = tmp[0]-'a'+1;
			int pow = 1;
			for(int m=1;m<i;m++) {
				pow *= 31;
				pow %= hmod;
				hsh[i][j][m] = hsh[i][j][m-1] + pow*(tmp[m]-'a'+1);
				hsh[i][j][m] %= hmod; 
			}
			//cout << i << " " << j << " " << hsh[i][j][i-1] << endl;
		}
	for(int i=1;i<=k;i++) dp[1][i] = 1;
	for(int i=2;i<=n;i++)
		for(int j=1;j<=k;j++) {
			int h1 = hsh[i][j][i-2];
			int h2 = hsh[i][j][i-1] - hsh[i][j][0];
			//cout << a[i][j] << " " << h1 << " " << h2 << endl;
			h2 += 2*hmod;
			h2 %= hmod;
			for(int m=1;m<=k;m++) {
				if(hsh[i-1][m][i-2] == h1) {
					dp[i][j] += dp[i-1][m];
					dp[i][j] %= mod;
				}
				else if((31*hsh[i-1][m][i-2])%hmod == h2) {
					dp[i][j] += dp[i-1][m];
					dp[i][j] %= mod;
				}
			}
		}
	int ans = 0;
	for(int i=1;i<=k;i++) {
		ans += dp[n][i];
		ans %= mod;
	}
	cout << ans << endl;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5868 KB Output is correct
2 Correct 7 ms 5868 KB Output is correct
3 Correct 7 ms 5868 KB Output is correct
4 Correct 10 ms 6104 KB Output is correct
5 Correct 9 ms 5948 KB Output is correct
6 Correct 9 ms 5868 KB Output is correct
7 Correct 10 ms 5868 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3052 KB Output is correct
2 Correct 2 ms 3052 KB Output is correct
3 Correct 2 ms 3052 KB Output is correct
4 Correct 2 ms 3052 KB Output is correct
5 Correct 7 ms 5868 KB Output is correct
6 Correct 7 ms 5868 KB Output is correct
7 Correct 7 ms 5868 KB Output is correct
8 Correct 10 ms 6104 KB Output is correct
9 Correct 9 ms 5948 KB Output is correct
10 Correct 9 ms 5868 KB Output is correct
11 Correct 10 ms 5868 KB Output is correct
12 Correct 375 ms 38932 KB Output is correct
13 Correct 337 ms 38912 KB Output is correct
14 Correct 364 ms 38892 KB Output is correct
15 Correct 334 ms 38916 KB Output is correct
16 Correct 864 ms 38892 KB Output is correct
17 Correct 353 ms 38892 KB Output is correct
18 Correct 353 ms 40624 KB Output is correct
19 Correct 366 ms 40556 KB Output is correct
20 Correct 363 ms 40628 KB Output is correct
21 Correct 355 ms 40684 KB Output is correct
22 Correct 846 ms 40772 KB Output is correct