oj.uz

Submission #223228

# Submission time Handle Problem Language Result Execution time Memory
223228 2020-04-15T05:40:51 Z dwsc Trener (COCI20_trener) C++14
110 / 110
 1103 ms 47276 KB 
#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

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3832 KB Output is correct
2 Correct 55 ms 3192 KB Output is correct
3 Correct 59 ms 3832 KB Output is correct
4 Correct 22 ms 384 KB Output is correct
5 Correct 55 ms 2544 KB Output is correct
6 Correct 53 ms 2552 KB Output is correct
7 Correct 23 ms 384 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 60 ms 3832 KB Output is correct
6 Correct 55 ms 3192 KB Output is correct
7 Correct 59 ms 3832 KB Output is correct
8 Correct 22 ms 384 KB Output is correct
9 Correct 55 ms 2544 KB Output is correct
10 Correct 53 ms 2552 KB Output is correct
11 Correct 23 ms 384 KB Output is correct
12 Correct 1061 ms 45900 KB Output is correct
13 Correct 1045 ms 46860 KB Output is correct
14 Correct 1103 ms 47276 KB Output is correct
15 Correct 1084 ms 46840 KB Output is correct
16 Correct 269 ms 376 KB Output is correct
17 Correct 983 ms 29688 KB Output is correct
18 Correct 992 ms 29176 KB Output is correct
19 Correct 1000 ms 29948 KB Output is correct
20 Correct 976 ms 29560 KB Output is correct
21 Correct 985 ms 30328 KB Output is correct
22 Correct 292 ms 372 KB Output is correct