oj.uz

Submission #223221

# Submission time Handle Problem Language Result Execution time Memory
223221 2020-04-15T05:33:23 Z cheeheng Trener (COCI20_trener) C++14
22 / 110
 13 ms 3840 KB 
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9+7;

int dp[55][1505];
char str[55];

string A[55][1505];

map<string, long long> m[55];

int main(){
    int N, K;
    scanf("%d%d", &N, &K);

    for(int i = 1; i <= N; i ++){
        for(int j = 0; j < K; j ++){
            memset(str, 0, sizeof(str));
            scanf(" %s", str);

            A[i][j] = string(str);

            if(i == 1){
                dp[i][j] = 1;
            }else{
                string str1 = A[i][j].substr(1);
                string str2 = A[i][j].substr(0, i-1);
                //printf("%s %s\n", str1.c_str(), str2.c_str());
                dp[i][j] = 0;
                if(m[i-1].find(str1) != m[i-1].end()){
                    dp[i][j] += m[i-1][str1];
                }

                if(m[i-1].find(str2) != m[i-1].end() && str1 != str2){
                    dp[i][j] += m[i-1][str2];
                }
            }

            dp[i][j] %= MOD;
            if(m[i].find(A[i][j]) == m[i].end()){
                m[i][A[i][j]] = dp[i][j];
            }else{
                m[i][A[i][j]] += dp[i][j];
            }
        }
    }

    long long ans = 0;
    for(int i = 0; i < K; i ++){
        ans += dp[N][i];
    }
    ans %= MOD;

    printf("%lld", ans);
    return 0;
}

Compilation message

trener.cpp: In function 'int main()':
trener.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &K);
     ~~~~~^~~~~~~~~~~~~~~~
trener.cpp:20:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %s", str);
             ~~~~~^~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3840 KB Output is correct
2 Correct 12 ms 3840 KB Output is correct
3 Correct 12 ms 3840 KB Output is correct
4 Incorrect 9 ms 3328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 6 ms 2944 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 13 ms 3840 KB Output is correct
6 Correct 12 ms 3840 KB Output is correct
7 Correct 12 ms 3840 KB Output is correct
8 Incorrect 9 ms 3328 KB Output isn't correct
9 Halted 0 ms 0 KB -