oj.uz

Submission #212590

# Submission time Handle Problem Language Result Execution time Memory
212590 2020-03-23T17:28:10 Z eggag32 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 7780 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int MOD = 1e9 + 7;
 
template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }
 
string s[55][1505];
ll dp[55][1505];
 
bool good(string b, string a){
    rep(i, b.size() - a.size() + 1) if(b.substr(i, a.size()) == a) return 1;
    return 0;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    int n, k;
    cin >> n >> k;
    rep(i, n) rep(j, k) cin >> s[i][j];
    rep(i, k) dp[0][i] = 1;
    repn(i, 1, n) rep(j, k) rep(l, k){
        if(good(s[i][j], s[i - 1][l])) dp[i][j] = (dp[i][j] + dp[i - 1][l]) % MOD;
    }
    ll ans = 0;
    rep(i, k) ans = (ans + dp[n - 1][i]) % MOD;
    cout << ans << endl;
    return 0;
}
/*
Things to look out for:
    - Integer overflows
    - Array bounds
    - Special cases
Be careful!
*/

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 3580 KB Output is correct
2 Correct 79 ms 3448 KB Output is correct
3 Correct 91 ms 3448 KB Output is correct
4 Correct 56 ms 3576 KB Output is correct
5 Correct 84 ms 3448 KB Output is correct
6 Correct 88 ms 3448 KB Output is correct
7 Correct 57 ms 3580 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 7 ms 2944 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 94 ms 3580 KB Output is correct
6 Correct 79 ms 3448 KB Output is correct
7 Correct 91 ms 3448 KB Output is correct
8 Correct 56 ms 3576 KB Output is correct
9 Correct 84 ms 3448 KB Output is correct
10 Correct 88 ms 3448 KB Output is correct
11 Correct 57 ms 3580 KB Output is correct
12 Execution timed out 2094 ms 7780 KB Time limit exceeded
13 Halted 0 ms 0 KB -