Submission #1086991

#TimeUsernameProblemLanguageResultExecution timeMemory
1086991underwaterkillerwhaleTrener (COCI20_trener)C++17
110 / 110
159 ms18572 KiB
#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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...