oj.uz

Submission #238437

# Submission time Handle Problem Language Result Execution time Memory
238437 2020-06-11T09:54:20 Z MishoKostov Trener (COCI20_trener) C++14
0 / 110
 183 ms 5060 KB 
#include<bits/stdc++.h>
#define endl "\n"

using namespace std;

const int nmax=2048, mod=1000000007;
int pi[nmax];
string a[64][nmax];
int n, m;
int r[nmax][nmax];

bool kmp(string s, string b)
{
    int x=s.size();
    s+="#"+b;
    //cout<<s<<endl;
    int sz=s.size();
    for(int i=1; i<sz; ++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;
        if(pi[i]==x) return true;
    }
    return false;
}

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

	cin>>n>>m;
	for(int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j) cin>>a[i][j];
    }
    if(n==1) cout<<m<<endl, exit(0);
    for(int i=0; i<m; ++i) r[0][i]=1;
    for(int i=0; i<n-1; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            for(int k=0; k<m; ++k)
            {
                if(kmp(a[i][j], a[i+1][k])) r[i+1][k]+=r[i][j], r[i+1][k]%=mod;
            }
        }
    }
    //for(int i=1; i<n; ++i, cout<<endl)
    //    for(int j=0; j<m; ++j) cout<<r[i][j]<<" ";
    int sum=0;
    for(int i=0; i<n; ++i) sum+=r[n-1][i], sum%=mod;
    cout<<sum<<endl;
 	return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 5060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4480 KB Output isn't correct
2 Halted 0 ms 0 KB -