oj.uz

Submission #1097542

# Submission time Handle Problem Language Result Execution time Memory
1097542 2024-10-07T14:43:49 Z hiensumi Trener (COCI20_trener) C++14
110 / 110
 30 ms 2908 KB 
#include <bits/stdc++.h>
using namespace std;
#define fod(i,a,b) for(int i = (int) (a); i <= (int) (b); i++)
#define fok(i,a,b) for(int i = (int) (a); i >= (int) (b); i--)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define el '\n'
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define mask(a) (1LL<<(a))
#define BIT(msk,i) (msk>>(i)&1LL)
using namespace std;
template <class T> bool mini(T &a, T b){ return (a > (b)) ? a = (b), 1 : 0; }
template <class T> bool maxi(T &a, T b){ return (a < (b)) ? a = (b), 1 : 0; }
#define name "trener"

const int MOD = 1e9 + 7;

inline void madd(int &a, int b){
    a += b;
    if(a >= MOD) a -= MOD;
    else if(a < 0) a += MOD;
}

int n, k;

unordered_map <string, int> dp;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
  
    cin >> n >> k;

    string s;
    fod(i,1,k){
        cin >> s;
        dp[s]++;
    }

    fod(i,2,n){
        unordered_map <string, int> new_dp;
        fod(j,1,k){
            string s; cin >> s;
            new_dp[s]++;
        }

        for(auto &x : new_dp){
            string x1 = x.fi.substr(0, i - 1);
            string x2 = x.fi.substr(1, i - 1);

            x.se = 1LL * x.se * (dp[x1] + (x1 != x2 ? dp[x2] : 0)) % MOD;
        }

        swap(dp, new_dp);
    }

    int res = 0;
    for(auto &x : dp) madd(res, x.se);

    cout << res;

    return 0;
}

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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
33.0 / 33.0

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

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 30 ms 2908 KB Output is correct
13 Correct 30 ms 2884 KB Output is correct
14 Correct 29 ms 2900 KB Output is correct
15 Correct 29 ms 2896 KB Output is correct
16 Correct 8 ms 2392 KB Output is correct
17 Correct 23 ms 2796 KB Output is correct
18 Correct 25 ms 2644 KB Output is correct
19 Correct 23 ms 2808 KB Output is correct
20 Correct 23 ms 2808 KB Output is correct
21 Correct 23 ms 2652 KB Output is correct
22 Correct 8 ms 2364 KB Output is correct