oj.uz

Submission #845613

# Submission time Handle Problem Language Result Execution time Memory
845613 2023-09-06T14:29:18 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 44 ms 14932 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));
    vector<map<string, ll> >m(n);
    for(ll i = 0; i < n; ++i)
    {
        for(ll j = 0; j < k; ++j)
        {
            cin >> v[i][j];
            m[i][v[i][j]]++;
        }
    }
    vector<map<string, ll> >dp(n);
    for(ll i = 0; i < k; ++i)dp[n - 1][v[n - 1][i]]++;

    for(ll i = n - 1; i >= 1; --i)
    {
        for(auto p : dp[i])
        {
            //cout << p.fi << ' ' << p.se << endl;
            string tmp{p.fi.begin(), p.fi.end() - 1};
            if(m[i - 1].count(tmp))
            {
                //cout << i << ' ' << p.fi << ' ' << tmp << ' ' << p.se << endl;
                dp[i - 1][tmp] += m[i - 1][tmp] * p.se % mod;
                dp[i - 1][tmp] %= mod;
            }
            if(tmp != string{p.fi.begin() + 1, p.fi.end()})
            {
                tmp = string{p.fi.begin() + 1, p.fi.end()};
                //cout << i << ' ' << p.fi << ' ' << tmp << ' ' << p.se << endl;
                if(m[i - 1].count(tmp))
                {
                    //cout << i << ' ' << p.fi << ' ' << tmp << ' ' << p.se << endl;
                    dp[i - 1][tmp] += m[i - 1][tmp] * p.se % mod;
                    dp[i - 1][tmp] %= mod;
                }
            }
        }
    }

    ll ans = 0;
    for(auto p : dp[0])
    {
        //cout << p.fi << ' ' << p.se << endl;
        ans += p.se;
        ans %= 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 0 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 344 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1368 KB Output is correct
2 Correct 2 ms 1368 KB Output is correct
3 Correct 2 ms 1384 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 1112 KB Output is correct
6 Correct 2 ms 1112 KB Output is correct
7 Correct 1 ms 600 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 344 KB Output is correct
5 Correct 3 ms 1368 KB Output is correct
6 Correct 2 ms 1368 KB Output is correct
7 Correct 2 ms 1384 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 2 ms 1112 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 42 ms 14932 KB Output is correct
13 Correct 44 ms 14928 KB Output is correct
14 Correct 41 ms 14932 KB Output is correct
15 Correct 44 ms 14928 KB Output is correct
16 Correct 10 ms 5464 KB Output is correct
17 Correct 38 ms 12880 KB Output is correct
18 Correct 38 ms 12880 KB Output is correct
19 Correct 38 ms 12880 KB Output is correct
20 Correct 38 ms 12880 KB Output is correct
21 Correct 38 ms 13036 KB Output is correct
22 Correct 11 ms 5468 KB Output is correct