Submission #238443

#	Time	Username	Problem	Language	Result	Execution time	Memory
238443		stev2005	Trener (COCI20_trener)	C++17	55 / 110	2091 ms	5536 KiB

trener

#include<iostream>
#include<cstring>
using namespace std;
const int mod=1000000007;
int n,k,dp[52][1510];
char c[52][1510][64];
void read()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        for(int j=0;j<k;j++)
            cin>>c[i][j];
}
int finds(char d[64],char e[64])
{
    int sz1=strlen(d);
    int sz2=strlen(e);
    bool l;
    for(int i=0;i<sz1-sz2+1;i++)
    {
        l=true;
        for(int j=0;j<sz2;j++)
            if(d[i+j]!=e[j])
        {
            l=false;
            break;
        }
        if(l)return 1;
    }
    return 0;
}
void solve()
{
    for(int i=0;i<k;i++)
		dp[0][i]=1;
	int rez;
	for(int i=1;i<n;i++)
		for(int j=0;j<k;j++)
			for(int p=0;p<k;p++)
			{
				rez=finds(c[i][j],c[i-1][p]);
				///cout<<rez<<' '<<c[i][j]<<' '<<c[i-1][p]<<endl;
				if(rez)dp[i][j]=(dp[i-1][p]%mod+dp[i][j]%mod)%mod;
			}
	int ans=0,pos=n-1;
	for(int i=0;i<k;i++)
		ans=(dp[pos][i]%mod+ans%mod)%mod;
	cout<<ans<<endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve();
return 0;
}

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