Submission #223228

#TimeUsernameProblemLanguageResultExecution timeMemory
223228dwscTrener (COCI20_trener)C++14
110 / 110
1103 ms47276 KiB
#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(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...