Submission #313527

#	Time	Username	Problem	Language	Result	Execution time	Memory
313527		kimbj0709	Trener (COCI20_trener)	C++14	110 / 110	987 ms	9208 KiB

trener

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int n,k;
  cin >> n >> k;
  string input;
  string arr[n+5][k+5];
  for(int i=0;i<n+5;i++){
    for(int j=0;j<k+5;j++){
      arr[i][j] = "1";
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<k;j++){
      cin >> input;
      arr[i][j] = input;
    }
  }
  int has[n+5][k+5];
  memset(has,0,sizeof(has));
  for(int i=0;i<k;i++){
    has[0][i] = 1;
  }
  for(int i=0;i<n-1;i++){
    map<string,set<int> > map1;
    for(int j=0;j<k;j++){
      if(arr[i+1][j]=="1"){
        continue;
      }
      string a = arr[i+1][j].substr(0,i+1);
      string b = arr[i+1][j].substr(1,i+1);
      if(map1.count(a)==0){
        map1.insert({a,{}});
      }
      if(map1.count(b)==0){
        map1.insert({b,{}});
      }
      map1[a].insert(j);
      map1[b].insert(j);
    }
    for(int j=0;j<k;j++){
      if(arr[i][j]=="1"){
        continue;
      }
      if(map1.count(arr[i][j])==0){
        continue;
      }
      for(auto l:map1[arr[i][j]]){
        has[i+1][l] += has[i][j];
        has[i+1][l] %= mod;
      }
    }
  }
  int ans = 0;
  for(int i=0;i<k;i++){
    ans += has[n-1][i];
    ans %= mod;
  }
  cout << ans;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55