oj.uz

Submission #345634

# Submission time Handle Problem Language Result Execution time Memory
345634 2021-01-07T17:28:48 Z limabeans Trener (COCI20_trener) C++17
55 / 110
 2000 ms 5900 KB 
#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.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 211 ms 3308 KB Output is correct
2 Correct 210 ms 3436 KB Output is correct
3 Correct 247 ms 3308 KB Output is correct
4 Correct 250 ms 3308 KB Output is correct
5 Correct 284 ms 3564 KB Output is correct
6 Correct 295 ms 3308 KB Output is correct
7 Correct 258 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 211 ms 3308 KB Output is correct
6 Correct 210 ms 3436 KB Output is correct
7 Correct 247 ms 3308 KB Output is correct
8 Correct 250 ms 3308 KB Output is correct
9 Correct 284 ms 3564 KB Output is correct
10 Correct 295 ms 3308 KB Output is correct
11 Correct 258 ms 3436 KB Output is correct
12 Execution timed out 2068 ms 5900 KB Time limit exceeded
13 Halted 0 ms 0 KB -