# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
530957 | 2022-02-27T08:10:34 Z | Tenis0206 | Trener (COCI20_trener) | C++11 | 2000 ms | 8672 KB |
#include <bits/stdc++.h> #define int long long using namespace std; const int Mod = 1e9 + 7; const int Mh = 666013; const int b = 29; int n,k; int dp[1505]; string s[1505]; map<int,int> dps,fc; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; for(int j=1; j<=k; j++) { cin>>s[j]; int Hash = 0; for(auto it : s[j]) { Hash = (1LL * Hash * b + (it - 'a' + 1)) % Mod; } ++dps[Hash]; } for(int i=2; i<=n; i++) { for(int j=1; j<=k; j++) { dp[j] = 0; } for(int j=1; j<=k; j++) { cin>>s[j]; fc.clear(); for(int st=0; st<s[j].size(); st++) { int Hash = 0; for(int dr=st; dr<s[j].size(); dr++) { Hash = (1LL * Hash * b + (s[j][dr] - 'a' + 1)) % Mod; if(!fc[Hash]) { dp[j] += dps[Hash]; dp[j] %= Mod; } ++fc[Hash]; } } } dps.clear(); for(int j=1; j<=k; j++) { int Hash = 0; for(auto it : s[j]) { Hash = (1LL * Hash * b + (it - 'a' + 1)) % Mod; } dps[Hash] += dp[j]; dps[Hash] %= Mod; } } int rez = 0; for(int j=1; j<=k; j++) { rez += dp[j]; rez %= Mod; } cout<<rez<<'\n'; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 826 ms | 2236 KB | Output is correct |
2 | Correct | 803 ms | 1804 KB | Output is correct |
3 | Correct | 806 ms | 2204 KB | Output is correct |
4 | Correct | 41 ms | 332 KB | Output is correct |
5 | Correct | 647 ms | 1344 KB | Output is correct |
6 | Correct | 647 ms | 1524 KB | Output is correct |
7 | Correct | 48 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 826 ms | 2236 KB | Output is correct |
6 | Correct | 803 ms | 1804 KB | Output is correct |
7 | Correct | 806 ms | 2204 KB | Output is correct |
8 | Correct | 41 ms | 332 KB | Output is correct |
9 | Correct | 647 ms | 1344 KB | Output is correct |
10 | Correct | 647 ms | 1524 KB | Output is correct |
11 | Correct | 48 ms | 376 KB | Output is correct |
12 | Execution timed out | 2092 ms | 8672 KB | Time limit exceeded |
13 | Halted | 0 ms | 0 KB | - |