oj.uz

Submission #219350

# Submission time Handle Problem Language Result Execution time Memory
219350 2020-04-05T07:26:55 Z NONAME Trener (COCI20_trener) C++17
55 / 110
 2000 ms 8208 KB 
#include <bits/stdc++.h>
#include <time.h>
//#include <random>
//#ifndef _LOCAL
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#endif
#define sz(x) int(x.size())
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define N 2 * 100500
#define oo ll(1e16)
#define pii pair <int, int>
#define pll pair <ll, ll>
#define ft first
#define sd second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define el '\n'
#define elf endl
#define base ll(1e9 + 7)
#define re return
#define nins 4294967295
using namespace std;
typedef long long ll;
typedef long double ld;

//mt19937 rnd(0);

ll n, m, dp[50][1500];
string s[50][1500];

void solve() {
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> s[i][j];

    for (int i = 0; i < m; i++)
        dp[0][i] = 1;

    for (int i = 0; i < n - 1; i++) {
        for (int j1 = 0; j1 < m; j1++)
        for (int j2 = 0; j2 < m; j2++)
            if (int(s[i + 1][j2].find(s[i][j1])) != -1)
                dp[i + 1][j2] += dp[i][j1], dp[i + 1][j2] %= base;
    }

    ll rs = 0;
    for (int i = 0; i < m; i++)
        rs += dp[n - 1][i], rs %= base;

    cout << rs;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifdef _LOCAL
        in("input.txt");

        int t = 1;
//        cin >> t;
        for (int i = 1; i <= t; i++) {
            cout << "Test #" << i << elf;

            clock_t start_time = clock();

            solve();

            cerr.precision(4); cerr << fixed;
            cerr << elf;
            cerr << "Time :: " << ld(clock() - start_time) / CLOCKS_PER_SEC << elf;

            cout << elf;
        }
    #else
        int t = 1;
//        cin >> t;

        while (t--) {
            solve();
            cout << el;
        }
    #endif
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3072 KB Output is correct
2 Correct 13 ms 3072 KB Output is correct
3 Correct 13 ms 3072 KB Output is correct
4 Correct 12 ms 3072 KB Output is correct
5 Correct 20 ms 3072 KB Output is correct
6 Correct 20 ms 3200 KB Output is correct
7 Correct 12 ms 3072 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 12 ms 3072 KB Output is correct
6 Correct 13 ms 3072 KB Output is correct
7 Correct 13 ms 3072 KB Output is correct
8 Correct 12 ms 3072 KB Output is correct
9 Correct 20 ms 3072 KB Output is correct
10 Correct 20 ms 3200 KB Output is correct
11 Correct 12 ms 3072 KB Output is correct
12 Correct 1401 ms 6180 KB Output is correct
13 Correct 1418 ms 7988 KB Output is correct
14 Correct 1390 ms 8208 KB Output is correct
15 Correct 1380 ms 8080 KB Output is correct
16 Correct 1142 ms 8108 KB Output is correct
17 Execution timed out 2092 ms 7816 KB Time limit exceeded
18 Halted 0 ms 0 KB -