oj.uz

Submission #845351

# Submission time Handle Problem Language Result Execution time Memory
845351 2023-09-06T13:15:23 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 6120 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];

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

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

    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];

    int dp[k +1];
    fill(dp, dp + k +1, 1);
    for(int i = 1; i <= n -1; i++)
    {
        int *dp2 = new int[k +1];
        memset(dp2, 0, sizeof (dp2));
        for(int j = 1; j <= k; j++)
        {
            for(int c = 1; c <= k; c++)
            {
                if(check(arr[i][j], arr[i +1][c])) 
                    dp2[c] = (dp2[c] + dp[j]) % MOD;
            }
        }

        memcpy(dp, dp2, sizeof dp);
    }

    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();
    }
}

Compilation message

trener.cpp: In function 'void solve()':
trener.cpp:51:24: warning: argument to 'sizeof' in 'void* memset(void*, int, size_t)' call is the same expression as the destination; did you mean to dereference it? [-Wsizeof-pointer-memaccess]
   51 |         memset(dp2, 0, sizeof (dp2));
      |                        ^~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3164 KB Output is correct
2 Correct 3 ms 3164 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 12 ms 3164 KB Output is correct
5 Correct 9 ms 3164 KB Output is correct
6 Correct 8 ms 3164 KB Output is correct
7 Correct 12 ms 3164 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 4 ms 3164 KB Output is correct
6 Correct 3 ms 3164 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 12 ms 3164 KB Output is correct
9 Correct 9 ms 3164 KB Output is correct
10 Correct 8 ms 3164 KB Output is correct
11 Correct 12 ms 3164 KB Output is correct
12 Correct 353 ms 5864 KB Output is correct
13 Correct 348 ms 5976 KB Output is correct
14 Correct 369 ms 6028 KB Output is correct
15 Correct 347 ms 5820 KB Output is correct
16 Execution timed out 2066 ms 6120 KB Time limit exceeded
17 Halted 0 ms 0 KB -