oj.uz

답안 #238440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -