oj.uz

Submission #845197

# Submission time Handle Problem Language Result Execution time Memory
845197 2023-09-06T12:32:45 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 330 ms 11096 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int MOD = 1e9 + 7;

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    #define OPEN freopen(".in", "r", stdin); \
                 freopen(".out", "w", stdout);
#else
    #define OPEN void(23);
#endif

string arr[55][105];
int dp[55][105][105];

bool check(string &a, string &b)
{
    int n = b.size(); 
    bool ok = true;
    for(int i = 1; i <= n -1; i++)
    {
        ok &= a[i -1] == b[i -1];
    }
    
    if(ok) return true;

    ok = true;
    for(int i = 2; i <= n; i++)
    {
        ok &= a[i -2] == b[i -1];
    }

    return ok;
}

void solve()
{
    memset(dp, -1, sizeof dp);
    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= k; j++)
            cin >> arr[i][j];

    function <int(int, int, int)> f = [&](int x, int bef, int nw) -> int
    {
        if(x == n) return check(arr[x -1][bef], arr[x][nw]);
        int &it = dp[x][bef][nw];
        if(it != -1) return it;

        if(!check(arr[x -1][bef], arr[x][nw])) return it = 0;
        //cerr << x << " " << bef << " " << nw << "\n";
        int res = 0;
        for(int i = 1; i <= k; i++)
        {
            int calc = f(x +1, nw, i);
            res = (res + calc) % MOD;
        }

        return it = res;
    };

    int cev = 0;
    for(int i = 1; i <= k; i++) 
        cev = (cev + f(1, 0, i)) % MOD;

    cout << cev;

    return;
}

int32_t main()
{
    OPEN;

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1; //cin >> t;
    while(t--)
    {
        solve();
    }
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5464 KB Output is correct
2 Correct 16 ms 5468 KB Output is correct
3 Correct 16 ms 5464 KB Output is correct
4 Correct 330 ms 5548 KB Output is correct
5 Correct 30 ms 5464 KB Output is correct
6 Correct 31 ms 5576 KB Output is correct
7 Correct 328 ms 5464 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 1 ms 5208 KB Output is correct
4 Correct 1 ms 5208 KB Output is correct
5 Correct 15 ms 5464 KB Output is correct
6 Correct 16 ms 5468 KB Output is correct
7 Correct 16 ms 5464 KB Output is correct
8 Correct 330 ms 5548 KB Output is correct
9 Correct 30 ms 5464 KB Output is correct
10 Correct 31 ms 5576 KB Output is correct
11 Correct 328 ms 5464 KB Output is correct
12 Runtime error 10 ms 11096 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -