oj.uz

Submission #238440

# Submission time Handle Problem Language Result Execution time Memory
238440 2020-06-11T09:58:06 Z MishoKostov Trener (COCI20_trener) C++14
55 / 110
 2000 ms 7504 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("-O3")
#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<m; ++i) sum+=r[n-1][i], sum%=mod;
    cout<<sum<<endl;
 	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 4924 KB Output is correct
2 Correct 173 ms 4984 KB Output is correct
3 Correct 173 ms 4728 KB Output is correct
4 Correct 218 ms 4856 KB Output is correct
5 Correct 246 ms 4984 KB Output is correct
6 Correct 247 ms 4856 KB Output is correct
7 Correct 214 ms 4856 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 6 ms 4480 KB Output is correct
3 Correct 7 ms 4480 KB Output is correct
4 Correct 7 ms 4480 KB Output is correct
5 Correct 189 ms 4924 KB Output is correct
6 Correct 173 ms 4984 KB Output is correct
7 Correct 173 ms 4728 KB Output is correct
8 Correct 218 ms 4856 KB Output is correct
9 Correct 246 ms 4984 KB Output is correct
10 Correct 247 ms 4856 KB Output is correct
11 Correct 214 ms 4856 KB Output is correct
12 Execution timed out 2080 ms 7504 KB Time limit exceeded
13 Halted 0 ms 0 KB -