Submission #453797

#	Time	Username	Problem	Language	Result	Execution time	Memory
453797		RGBB	Trener (COCI20_trener)	C++14	110 / 110	612 ms	3528 KiB

trener

#include <iostream>
#include <bits/stdc++.h>
#include <bitset>
using namespace std;
long prime=1000000007;
long base[50];
int main()
{
  	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;int k;
    cin>>n>>k;
    base[0]=1;
		for(int i=1;i<n;i++)base[i]=(26*base[i-1])%prime;
		int input[n][k][3];
		for(int i=0;i<n;i++)
		{
			for(int y=0;y<k;y++)
      {
        string a;cin>>a;
        long hash=0;
	    	int size=a.length();
	    	for(int i=0;i<size-1;i++)hash=(26*hash+a.at(i)  -'a')%prime;
	    	input[i][y][0]=hash;
	     	hash=(26*hash+a.at(size-1)-'a')%prime;
	    	input[i][y][2]=hash;
		    hash=(hash-(a.at(0)-'a')*base[size-1])%prime;
	  	  if(hash<0)hash+=prime;
	    	input[i][y][1]=hash;
      }
		}
    int dp[n][k];
		for(int i=0;i<k;i++)dp[0][i]=1;
    for(int i=1;i<n;i++)for(int y=0;y<k;y++)dp[i][y]=0;
		for(int i=0;i<n-1;i++)
		{
			for(int x=0;x<k;x++)
			{
				for(int y=0;y<k;y++)
				{
					if(input[i][x][2]==input[i+1][y][0]||input[i][x][2]==input[i+1][y][1])dp[i+1][y]=(dp[i+1][y]+dp[i][x])%prime;
				}
			}
		}
		int output=0;
		for(int i=0;i<k;i++)output=(output+dp[n-1][i])%prime;
		cout<<output;
}

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