Submission #345634

#	Time	Username	Problem	Language	Result	Execution time	Memory
345634		limabeans	Trener (COCI20_trener)	C++17	55 / 110	2068 ms	5900 KiB

trener

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;
const ll mod = 1e9 + 7;



void add(ll &x, ll y) {
    x %= mod;
    x += y;
    x %= mod;
    y %= mod;
}





// s inside t ?
bool inside(string s, string t) {
    //return t.find(s) != std::string::npos;
    string S  = s+"#"+t;
    int n = S.length();
    vector<int> pi(n);
    for (int i=1; i<n; i++) {
	int j=pi[i-1];
	while (j>0 && S[i]!=S[j]) {
	    j = pi[j-1];
	}
	if (S[i]==S[j]) j++;
	pi[i] = j;
    }

    for (int i=0; i<n; i++) {
	if (pi[i] == (int)s.length()) return true;
    }

    return false;
}

int n, k;
string g[55][1505];
ll dp[55][1505];


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

    cin>>n>>k;
    for (int i=0; i<n; i++) {
	for (int j=0; j<k; j++) {
	    cin>>g[i][j];
	}
    }

    for (int j=0; j<k; j++) {
	dp[0][j] = 1;
    }

    for (int i=1; i<n; i++) {
	for (int p=0; p<k; p++) {
	    for (int j=0; j<k; j++) {
		if (inside(g[i-1][p], g[i][j])) {
		    add(dp[i][j], dp[i-1][p]);
		}
	    }
	}
    }


    
    ll res = 0;
    for (int j=0; j<k; j++) {
	add(res, dp[n-1][j]);
    }


    cout<<res<<endl;    
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 55