oj.uz

Submission #845248

# Submission time Handle Problem Language Result Execution time Memory
845248 2023-09-06T12:48:42 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 6648 KB 
#include <bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define int long long
using namespace std;

const int inf = 2e18 + 5;
const int N = 5e3 + 5;
const int mod = 1e9 + 7;

int32_t main(){
  //freopen("in.txt","r", stdin);
  int n, k;
  cin>>n>>k;
  vector<vector<string> > a(n, vector<string>(k));
  for(int i = 0; i < n; i++){
    for(int j = 0; j < k; j++){
        cin>>a[i][j];
    }
  }
  vector<vector<int> > dp(n+1, vector<int>(k));
  for(int i = 0; i < k; i++){
    dp[0][i] = 1;
  }

  for(int i = 0; i < n-1; i++){
    for(int j = 0; j < k; j++){
        for(int l = 0; l < k; l++){
            if((a[i][j] == a[i+1][l].substr(0, a[i+1][l].size()-1) || a[i][j] == a[i+1][l].substr(1, a[i+1][l].size()-1))){
                dp[i+1][l] += dp[i][j];
                dp[i+1][l] %= mod;
            }
        }
    }
  }

  int s = 0;
  for(int i = 0; i < k; i++){
    s = (s + dp[n-1][i])%mod;
  }
  cout<<s<<endl;
  return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 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 24 ms 600 KB Output is correct
2 Correct 23 ms 600 KB Output is correct
3 Correct 24 ms 864 KB Output is correct
4 Correct 14 ms 856 KB Output is correct
5 Correct 25 ms 600 KB Output is correct
6 Correct 26 ms 860 KB Output is correct
7 Correct 15 ms 860 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 24 ms 600 KB Output is correct
6 Correct 23 ms 600 KB Output is correct
7 Correct 24 ms 864 KB Output is correct
8 Correct 14 ms 856 KB Output is correct
9 Correct 25 ms 600 KB Output is correct
10 Correct 26 ms 860 KB Output is correct
11 Correct 15 ms 860 KB Output is correct
12 Execution timed out 2004 ms 6648 KB Time limit exceeded
13 Halted 0 ms 0 KB -