oj.uz

Submission #223207

# Submission time Handle Problem Language Result Execution time Memory
223207 2020-04-15T05:13:07 Z lyc Trener (COCI20_trener) C++14
55 / 110
 2000 ms 5844 KB 
#include <bits/stdc++.h>
using namespace std;

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 55;
const int MX_K = 1505;

const int MOD = 1e9+7;

int N, K;
string S[MX_N][MX_K];

int dp[MX_N][MX_K];

vector<int> build_table(string W) {
    vector<int> T(W.length()+1);
    int pos = 1;    // the current position we are computing in T
    int cnd = 0;    // the zero-based index in W of the next character of the current candidate substring

    T[0] = -1;

    while (pos < (int)W.length()) {
        if (W[pos] == W[cnd])
            T[pos] = T[cnd];
        else {
            T[pos] = cnd;
            cnd = T[cnd]; // (to increase performance)
            while (cnd >= 0 and W[pos] != W[cnd]) {
                cnd = T[cnd];
            }
        }
        pos = pos + 1, cnd = cnd + 1;
    }
    T[pos] = cnd; // (only need when all word occurrences searched)

    return T;
}

bool search(string S, string W, vector<int>& T) {
    int P[S.length()];
    int nP;

    int j = 0;
    int k = 0;
    
    nP = 0;

    while (j < (int)S.length()) {
        if (W[k] == S[j]) {
            j = j + 1;
            k = k + 1;
            if (k == (int)W.length()) {
                // (occurrence found, if only first occurrence is needed, m <- j - k  may be returned here)
                P[nP] = j - k, nP = nP + 1;
                k = T[k]; // (T[length(W)] can't be -1)
            }
        }
        else {
            k = T[k];
            if (k < 0) {
                j = j + 1;
                k = k + 1;
            }
        }
    }

    return nP > 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    FOR(i,1,N){
        FOR(j,1,K) cin >> S[i][j];
    }

    FOR(j,1,K) dp[N][j] = 1;
    RFOR(i,N-1,1){
        FOR(j,1,K){
            dp[i][j] = 0;

            vector<int> T = build_table(S[i][j]);

            FOR(k,1,K) {
                if (search(S[i+1][k], S[i][j], T)) {
                    //cout << i << " " << j << " :: " << i+1 << " " << k << endl;
                    dp[i][j] += dp[i+1][k];
                    if (dp[i][j] >= MOD) dp[i][j] -= MOD;
                }
            }
        }
    }

    int ans = 0;
    FOR(i,1,K){
        ans += dp[1][i];
        if (ans >= MOD) ans -= MOD;
    }
    cout << ans << '\n';
}

Compilation message

trener.cpp: In function 'bool search(std::__cxx11::string, std::__cxx11::string, std::vector<int>&)':
trener.cpp:43:9: warning: variable 'P' set but not used [-Wunused-but-set-variable]
     int P[S.length()];
         ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 6 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 82 ms 3320 KB Output is correct
2 Correct 80 ms 3320 KB Output is correct
3 Correct 86 ms 3448 KB Output is correct
4 Correct 61 ms 3320 KB Output is correct
5 Correct 125 ms 3320 KB Output is correct
6 Correct 115 ms 3320 KB Output is correct
7 Correct 59 ms 3320 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 6 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 82 ms 3320 KB Output is correct
6 Correct 80 ms 3320 KB Output is correct
7 Correct 86 ms 3448 KB Output is correct
8 Correct 61 ms 3320 KB Output is correct
9 Correct 125 ms 3320 KB Output is correct
10 Correct 115 ms 3320 KB Output is correct
11 Correct 59 ms 3320 KB Output is correct
12 Execution timed out 2090 ms 5844 KB Time limit exceeded
13 Halted 0 ms 0 KB -