oj.uz

Submission #530941

# Submission time Handle Problem Language Result Execution time Memory
530941 2022-02-27T07:31:35 Z Servus2022 Trener (COCI20_trener) C++14
110 / 110
 298 ms 26104 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 1e9 + 7;

int N, K;
map <string, int> dp;
map <string, int> lg;

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;
}

void Solve () {
    for (int i = 1; i <= N; ++ i ) {
        for (int j = 1; j <= K; ++ j ) {
            string S;
            cin >> S;

            if (i == 1) {
                dp[S] ++;
                lg[S] = 1;
                continue;
            }
            string primul, aldoilea;
            for (int k = 0; k < S.size()-1; ++ k ) {
                primul.push_back(S[k]);
                aldoilea.push_back(S[k+1]);
            }

            if (primul == aldoilea) {
                if (lg[primul] == i-1) {
                    lg[S] = i;
                    dp[S] = (dp[S] + dp[primul]) % MOD;
                }

                continue;
            }

            if (lg[primul] == i-1) {
                lg[S] = i;
                dp[S] = (dp[S] + dp[primul]) % MOD;
            }

            if (lg[aldoilea] == i-1) {
                lg[S] = i;
                dp[S] = (dp[S] + dp[aldoilea]) % MOD;
            }
        }
    }

    int ans = 0;
    for (auto it : dp) {
        if (lg[it.first] == N) ans = (ans + it.second) % MOD;
    }

    cout << ans << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

Compilation message

trener.cpp: In function 'void Solve()':
trener.cpp:30:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             for (int k = 0; k < S.size()-1; ++ k ) {
      |                             ~~^~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1960 KB Output is correct
2 Correct 12 ms 1996 KB Output is correct
3 Correct 13 ms 1988 KB Output is correct
4 Correct 4 ms 448 KB Output is correct
5 Correct 12 ms 1532 KB Output is correct
6 Correct 12 ms 1608 KB Output is correct
7 Correct 4 ms 448 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 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 12 ms 1960 KB Output is correct
6 Correct 12 ms 1996 KB Output is correct
7 Correct 13 ms 1988 KB Output is correct
8 Correct 4 ms 448 KB Output is correct
9 Correct 12 ms 1532 KB Output is correct
10 Correct 12 ms 1608 KB Output is correct
11 Correct 4 ms 448 KB Output is correct
12 Correct 298 ms 26104 KB Output is correct
13 Correct 293 ms 26020 KB Output is correct
14 Correct 278 ms 25716 KB Output is correct
15 Correct 270 ms 25528 KB Output is correct
16 Correct 48 ms 2208 KB Output is correct
17 Correct 248 ms 18600 KB Output is correct
18 Correct 242 ms 18804 KB Output is correct
19 Correct 240 ms 18828 KB Output is correct
20 Correct 245 ms 18816 KB Output is correct
21 Correct 240 ms 18752 KB Output is correct
22 Correct 52 ms 2216 KB Output is correct