Submission #223228

#	Time	Username	Problem	Language	Result	Execution time	Memory
223228		dwsc	Trener (COCI20_trener)	C++14	110 / 110	1103 ms	47276 KiB

trener

#include <bits/stdc++.h>
#define int long long
using namespace std;
map<string,int> s;
int n,k;
int pos[55][55];
int memo[55][55];
int MOD = 1e9+7;
string cur;
int dp(int i,int j){
    if (i == j) return pos[i][j];
    if (memo[i][j] != -1) return memo[i][j];
    int ans = 0;
    if (pos[i][j]){
        int same = 1;
        for (int l = i; l < j; l++){
            if (cur[l] != cur[l+1]){
                same = 0;
                break;
            }
        }
        ans = (ans+dp(i+1,j))%MOD;
        if (!same)ans = (ans+dp(i,j-1))%MOD;
        //cout << i << " " << j << " " << same << "hi\n";
    }
    //cout << i << " " << j << " " << ans << "\n";
    return memo[i][j] = (ans*pos[i][j])%MOD;
}
main(){
    cin >> n >> k;
    for (int i = 1; i <= n-1; i++){
        for (int j = 0; j < k; j++){
            string x;
            cin >> x;
            s[x]++;
        }
    }
    int ans = 0;
    for (int i = 0; i < k; i++){
        cin >> cur;
        for (int j = 0; j < 55; j++) for (int l = 0; l < 55; l++){memo[j][l] = -1; pos[j][l] = 0;}
        for (int j = 0; j < n; j++){
            string temp = "";
            for (int l = j; l < n; l++){
                temp += cur[l];
                pos[j][l] = s[temp];
            }
        }
        pos[0][n-1] = 1;
        ans = (ans+dp(0,n-1))%MOD;
    }
    cout << ans;
}

Compilation message (stderr)

trener.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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