oj.uz

Submission #845275

# Submission time Handle Problem Language Result Execution time Memory
845275 2023-09-06T12:56:02 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 472 ms 27176 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));
  map<string, vector<int> > mp;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < k; j++){
        cin>>a[i][j];
        mp[a[i][j]].pb(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++){
        string s1 = a[i+1][j].substr(0, a[i+1][j].size()-1);
        string s2 = a[i+1][j].substr(1, a[i+1][j].size()-1);

        for(auto itr: mp[s1]){
            dp[i+1][j] = (dp[i+1][j] + dp[i][itr])%mod;
            //cout<<s1<<" "<<itr<<endl;
        }

        if(s1 == s2) continue;
        for(auto itr: mp[s2]){
            dp[i+1][j] = (dp[i+1][j] + dp[i][itr])%mod;
            //cout<<s2<<" "<<itr<<endl;
        }
    }
  }

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2392 KB Output is correct
2 Correct 8 ms 2136 KB Output is correct
3 Correct 10 ms 2136 KB Output is correct
4 Correct 5 ms 856 KB Output is correct
5 Correct 7 ms 1624 KB Output is correct
6 Correct 9 ms 1624 KB Output is correct
7 Correct 5 ms 860 KB Output is correct

Subtask #3
55.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 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 9 ms 2392 KB Output is correct
6 Correct 8 ms 2136 KB Output is correct
7 Correct 10 ms 2136 KB Output is correct
8 Correct 5 ms 856 KB Output is correct
9 Correct 7 ms 1624 KB Output is correct
10 Correct 9 ms 1624 KB Output is correct
11 Correct 5 ms 860 KB Output is correct
12 Correct 217 ms 26964 KB Output is correct
13 Correct 220 ms 26912 KB Output is correct
14 Correct 271 ms 27048 KB Output is correct
15 Correct 217 ms 27176 KB Output is correct
16 Correct 460 ms 7580 KB Output is correct
17 Correct 262 ms 20316 KB Output is correct
18 Correct 224 ms 20560 KB Output is correct
19 Correct 178 ms 20480 KB Output is correct
20 Correct 184 ms 20592 KB Output is correct
21 Correct 233 ms 20568 KB Output is correct
22 Correct 472 ms 7504 KB Output is correct