oj.uz

답안 #453797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
453797 2021-08-04T21:50:18 Z RGBB Trener (COCI20_trener) C++14
110 / 110
 612 ms 3528 KB 
#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.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 5 ms 520 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 5 ms 460 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 5 ms 520 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 5 ms 460 KB Output is correct
12 Correct 158 ms 3404 KB Output is correct
13 Correct 156 ms 3348 KB Output is correct
14 Correct 154 ms 3336 KB Output is correct
15 Correct 156 ms 3412 KB Output is correct
16 Correct 612 ms 3528 KB Output is correct
17 Correct 174 ms 3512 KB Output is correct
18 Correct 174 ms 3352 KB Output is correct
19 Correct 172 ms 3396 KB Output is correct
20 Correct 180 ms 3312 KB Output is correct
21 Correct 174 ms 3524 KB Output is correct
22 Correct 606 ms 3476 KB Output is correct