oj.uz

Submission #845215

# Submission time Handle Problem Language Result Execution time Memory
845215 2023-09-06T12:38:28 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 1000 ms 132688 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 2000, M = 1e5+10, K = 18;



ll n, k, dp[N][N], H[N][N], p[N];
string s[N][N];
  
bool subseq(int i, int j, int i1, int j1){
  ll h = H[i][j];
  ll h1 = H[i1][j1];
  if((h * p[1]) % MOD == (h1 - (s[i1][j1][0] - 'a' + 1) + MOD) % MOD) return 1;
  if(h == (((h1 - (s[i1][j1][i1 - 1] - 'a' + 1) * p[i1 - 1]) % MOD) + MOD) % MOD) return 1;
  return 0;
}

void solve(){
  p[0] = 1;
  for(int i = 1; i < N; ++i) p[i] = (p[i-1] * 37) % MOD;
  cin >> n >> k;
  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= k; ++j){
      cin >> s[i][j];
      H[i][j] = 0;
      for(int l = 0; l < i; ++l){
        H[i][j] += p[l] * (s[i][j][l] - 'a' + 1);
        H[i][j] %= MOD;
      }
    }
  }
  
  for(int i = 1; i <= n; ++i) for(int j = 0; j <= k; ++j) dp[i][j] = (n == i);
  for(int i = n - 1; i >= 1; --i){
    for(int j = 1; j <= k; ++j){
      for(int to = 1; to <= k; ++to){
        if(subseq(i, j, i + 1, to)){
          dp[i][j] += dp[i + 1][to];
          dp[i][j] -= dp[i][j] >= MOD ? MOD : 0;
        }
      }
    }
  }
  ll ans = 0;
  for(int i = 1; i <= k; ++i) (ans+=dp[1][i])%=MOD;
  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> tt;
  while(tt--){
    solve();
    // en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

trener.cpp: In function 'int main()':
trener.cpp:59:15: warning: unused variable 'aa' [-Wunused-variable]
   59 |   int tt = 1, aa;
      |               ^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 127832 KB Output is correct
2 Correct 24 ms 127832 KB Output is correct
3 Correct 25 ms 127832 KB Output is correct
4 Correct 24 ms 127832 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 129880 KB Output is correct
2 Correct 31 ms 129880 KB Output is correct
3 Correct 31 ms 129880 KB Output is correct
4 Correct 30 ms 129880 KB Output is correct
5 Correct 30 ms 129880 KB Output is correct
6 Correct 32 ms 129872 KB Output is correct
7 Correct 29 ms 129880 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 127832 KB Output is correct
2 Correct 24 ms 127832 KB Output is correct
3 Correct 25 ms 127832 KB Output is correct
4 Correct 24 ms 127832 KB Output is correct
5 Correct 30 ms 129880 KB Output is correct
6 Correct 31 ms 129880 KB Output is correct
7 Correct 31 ms 129880 KB Output is correct
8 Correct 30 ms 129880 KB Output is correct
9 Correct 30 ms 129880 KB Output is correct
10 Correct 32 ms 129872 KB Output is correct
11 Correct 29 ms 129880 KB Output is correct
12 Correct 941 ms 132688 KB Output is correct
13 Correct 935 ms 132616 KB Output is correct
14 Correct 938 ms 132608 KB Output is correct
15 Correct 937 ms 132612 KB Output is correct
16 Correct 596 ms 132688 KB Output is correct
17 Correct 939 ms 132616 KB Output is correct
18 Correct 1000 ms 132688 KB Output is correct
19 Correct 971 ms 132608 KB Output is correct
20 Correct 947 ms 132616 KB Output is correct
21 Correct 943 ms 132612 KB Output is correct
22 Correct 593 ms 132432 KB Output is correct