oj.uz

Submission #1086991

# Submission time Handle Problem Language Result Execution time Memory
1086991 2024-09-12T02:22:14 Z underwaterkillerwhale Trener (COCI20_trener) C++17
110 / 110
 159 ms 18572 KB 
#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 50 + 7;
const int M = 2e3 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 350;

int n, K;
string a[M];
map<string, int> pdp, dp;

void solution() {
    cin >> n >> K;
    rep (i, 1, n) {
        rep (j, 1, K) cin >> a[j];
        rep (j, 1, K) {
            string &s = a[j];
            if (i == 1) dp[s]++;
            else {
                string s1, s2;
                s1 = s.substr(1, SZ(s) - 1);
                s2 = s.substr(0, SZ(s) - 1);
                if (s1 != s2) dp[s] = ((dp[s] + pdp[s1]) % Mod + pdp[s2]) % Mod;
                else dp[s] = (dp[s] + pdp[s1]) % Mod;
            }
        }
        rep (j, 1, K) {
            pdp[a[j]] = dp[a[j]];
//            cout << a[j] <<": "<<pdp[a[j]] <<"\n";
        }
        dp.clear();
    }
    sort (a + 1, a + 1 + K);
    K = unique(a + 1, a + 1 + K) - a - 1;
    int res = 0;
    rep (i, 1, K) res = (res + pdp[a[i]]) % Mod;
    cout << res <<"\n";

}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug +7
5 3 1
1 1 1 2 3
2 3 5
1 2
2 3
2 4
1 5
2 3
*/

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1628 KB Output is correct
2 Correct 6 ms 1604 KB Output is correct
3 Correct 6 ms 1628 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 6 ms 1368 KB Output is correct
6 Correct 5 ms 1368 KB Output is correct
7 Correct 1 ms 604 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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 6 ms 1604 KB Output is correct
7 Correct 6 ms 1628 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 5 ms 1368 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 150 ms 18572 KB Output is correct
13 Correct 159 ms 18516 KB Output is correct
14 Correct 148 ms 18512 KB Output is correct
15 Correct 146 ms 18564 KB Output is correct
16 Correct 14 ms 2580 KB Output is correct
17 Correct 124 ms 13236 KB Output is correct
18 Correct 116 ms 13680 KB Output is correct
19 Correct 118 ms 13396 KB Output is correct
20 Correct 122 ms 13392 KB Output is correct
21 Correct 117 ms 13352 KB Output is correct
22 Correct 15 ms 2392 KB Output is correct