oj.uz

Submission #845213

# Submission time Handle Problem Language Result Execution time Memory
845213 2023-09-06T12:37:13 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 493320 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][1505];
int dp[55][1505][1505];

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 69 ms 490664 KB Output is correct
2 Correct 59 ms 490460 KB Output is correct
3 Correct 53 ms 490384 KB Output is correct
4 Correct 55 ms 490580 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 490688 KB Output is correct
2 Correct 70 ms 490836 KB Output is correct
3 Correct 68 ms 490784 KB Output is correct
4 Correct 395 ms 490780 KB Output is correct
5 Correct 96 ms 490640 KB Output is correct
6 Correct 82 ms 490784 KB Output is correct
7 Correct 374 ms 490580 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 490664 KB Output is correct
2 Correct 59 ms 490460 KB Output is correct
3 Correct 53 ms 490384 KB Output is correct
4 Correct 55 ms 490580 KB Output is correct
5 Correct 68 ms 490688 KB Output is correct
6 Correct 70 ms 490836 KB Output is correct
7 Correct 68 ms 490784 KB Output is correct
8 Correct 395 ms 490780 KB Output is correct
9 Correct 96 ms 490640 KB Output is correct
10 Correct 82 ms 490784 KB Output is correct
11 Correct 374 ms 490580 KB Output is correct
12 Execution timed out 2054 ms 493320 KB Time limit exceeded
13 Halted 0 ms 0 KB -