oj.uz

Submission #373072

# Submission time Handle Problem Language Result Execution time Memory
373072 2021-03-03T09:03:02 Z Nimbostratus Trener (COCI20_trener) C++17
55 / 110
 2000 ms 8428 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 int
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;

int n,k;
string a[maxn][maxk];
int dp[maxn][maxk];

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];
	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++) {
			string sub1 = a[i][j].substr(0,i-1);
			string sub2 = a[i][j].substr(1,i-1);
			for(int m=1;m<=k;m++)
				if(a[i-1][m] == sub1 or a[i-1][m] == sub2) {
					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 2924 KB Output is correct
2 Correct 2 ms 2924 KB Output is correct
3 Correct 2 ms 2924 KB Output is correct
4 Correct 2 ms 2924 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3436 KB Output is correct
2 Correct 11 ms 3436 KB Output is correct
3 Correct 11 ms 3436 KB Output is correct
4 Correct 7 ms 3436 KB Output is correct
5 Correct 15 ms 3496 KB Output is correct
6 Correct 15 ms 3436 KB Output is correct
7 Correct 7 ms 3436 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2924 KB Output is correct
2 Correct 2 ms 2924 KB Output is correct
3 Correct 2 ms 2924 KB Output is correct
4 Correct 2 ms 2924 KB Output is correct
5 Correct 10 ms 3436 KB Output is correct
6 Correct 11 ms 3436 KB Output is correct
7 Correct 11 ms 3436 KB Output is correct
8 Correct 7 ms 3436 KB Output is correct
9 Correct 15 ms 3496 KB Output is correct
10 Correct 15 ms 3436 KB Output is correct
11 Correct 7 ms 3436 KB Output is correct
12 Correct 1567 ms 8428 KB Output is correct
13 Correct 1534 ms 8352 KB Output is correct
14 Correct 1523 ms 7916 KB Output is correct
15 Correct 1605 ms 8108 KB Output is correct
16 Correct 793 ms 8300 KB Output is correct
17 Execution timed out 2081 ms 8048 KB Time limit exceeded
18 Halted 0 ms 0 KB -