oj.uz

Submission #845545

# Submission time Handle Problem Language Result Execution time Memory
845545 2023-09-06T14:04:50 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 7256 KB 
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
#define pb push_back
#define endl '\n'
#define fi first
#define se second
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define CDIV(a,b) (((a)+(b)-(1))/(b))
const ll inf = 1e17 + 5;
const ll mod = 1e9 + 7;
const ll N = 1e3 + 30;

 
ll mod_(ll a, ll b)
{
    if(a >= 0)return a % b;
    a += (-a/b + 1) * b;
    return a % b;
}

void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<vector<string> >v(n, vector<string>(k));
    for(ll i = 0; i < n; ++i)
    {
        for(ll j = 0; j < k; ++j)
            cin >> v[i][j];
    }
    vector<vector<ll> >dp(n, vector<ll>(k));
    for(ll i = k - 1; i >= 0; --i)dp[n - 1][i] = 1;
    for(ll i = n - 1; i >= 1; --i)
    {
        for(ll j = 0; j < k; ++j)
        {
            for(ll z = 0; z < k; ++z)
            {
                if(v[i - 1][z] == string{v[i][j].begin(), v[i][j].end() - 1})
                {
                    dp[i - 1][z] += dp[i][j];
                    if(dp[i - 1][z] >= mod)dp[i - 1][z] %= mod;
                }
                else if(v[i - 1][z] == string{v[i][j].begin() + 1, v[i][j].end()})
                {
                    dp[i - 1][z] += dp[i][j];
                    if(dp[i - 1][z] >= mod)dp[i - 1][z] %= mod;
                }
                
                
            }
        }
    }
    ll ans = 0;
    for(ll i = 0; i < k; ++i) ans = (ans + dp[0][i]) % mod;
    cout << ans << endl;
    

}
    
int main()
{
    fio;
    //ll t; cin >> t; while(t--)
    {
        solve();
    }
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 600 KB Output is correct
2 Correct 20 ms 600 KB Output is correct
3 Correct 20 ms 812 KB Output is correct
4 Correct 12 ms 600 KB Output is correct
5 Correct 20 ms 856 KB Output is correct
6 Correct 20 ms 972 KB Output is correct
7 Correct 12 ms 860 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 20 ms 600 KB Output is correct
6 Correct 20 ms 600 KB Output is correct
7 Correct 20 ms 812 KB Output is correct
8 Correct 12 ms 600 KB Output is correct
9 Correct 20 ms 856 KB Output is correct
10 Correct 20 ms 972 KB Output is correct
11 Correct 12 ms 860 KB Output is correct
12 Execution timed out 2021 ms 7256 KB Time limit exceeded
13 Halted 0 ms 0 KB -