oj.uz

Submission #846012

# Submission time Handle Problem Language Result Execution time Memory
846012 2023-09-07T05:59:51 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 308 ms 10852 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

int mods[] = {232323233, 232323323, 323232323};
int primes[] = {23 + 6, 23 + 14, 23 + 20};

string arr[55][1505];
array <int, 3> all[55][1505], sol[55][1505], sag[55][1505];

array <int, 3> hashle(string a)
{
    int n = a.size();
    array <int, 3> vals = {0, 0, 0};
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            vals[j] = (vals[j] * primes[j] + (a[i] - 'a' +1)) % mods[j];
        }
    }

    return vals;
}

bool operator== (array <int, 3> &a, array <int, 3> &b)
{
    bool ok = true;
    for(int i = 0; i < 3; i++) ok &= a[i] == b[i];

    return ok;
}

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

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            all[i][j] = hashle(arr[i][j]);
            sol[i][j] = hashle(arr[i][j].substr(0, i -1));
            sag[i][j] = hashle(arr[i][j].substr(1, i -1));
        }
    }

    vector <int> dp(k +1, 1);
    for(int i = 1; i <= n -1; i++)
    {
        vector <int> dp2(k +1);
        for(int j = 1; j <= k; j++)
        {
            for(int c = 1; c <= k; c++)
            {
                if(all[i][j] == sol[i +1][c] || all[i][j] == sag[i +1][c]) 
                    dp2[c] = (dp2[c] + dp[j]) % MOD;
            }
        }

        swap(dp, dp2);
    }

    int cev = 0;
    for(int i = 1; i <= k; i++) cev = (cev + dp[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 1 ms 5720 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6232 KB Output is correct
2 Correct 8 ms 5980 KB Output is correct
3 Correct 8 ms 6152 KB Output is correct
4 Correct 8 ms 5980 KB Output is correct
5 Correct 8 ms 5908 KB Output is correct
6 Correct 8 ms 5980 KB Output is correct
7 Correct 8 ms 5980 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 9 ms 6232 KB Output is correct
6 Correct 8 ms 5980 KB Output is correct
7 Correct 8 ms 6152 KB Output is correct
8 Correct 8 ms 5980 KB Output is correct
9 Correct 8 ms 5908 KB Output is correct
10 Correct 8 ms 5980 KB Output is correct
11 Correct 8 ms 5980 KB Output is correct
12 Correct 218 ms 10616 KB Output is correct
13 Correct 225 ms 10604 KB Output is correct
14 Correct 216 ms 10600 KB Output is correct
15 Correct 231 ms 10604 KB Output is correct
16 Correct 290 ms 10788 KB Output is correct
17 Correct 222 ms 10504 KB Output is correct
18 Correct 224 ms 10604 KB Output is correct
19 Correct 224 ms 10608 KB Output is correct
20 Correct 223 ms 10604 KB Output is correct
21 Correct 228 ms 10852 KB Output is correct
22 Correct 308 ms 10556 KB Output is correct