Submission #250878

#	Time	Username	Problem	Language	Result	Execution time	Memory
250878		44442	Trener (COCI20_trener)	C++11	110 / 110	390 ms	35064 KiB

trener

#include<bits/stdc++.h>
using namespace std;
long long n,k,ok[104][1504],mod,okk;
string str[104][1504],x,y;
map<string,long long>m,num;
set<string>ss;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
for(int i=1;i<n+1;i++){
	 for(int j=1;j<k+1;j++){
	 	 cin>>str[i][j];
	 	 ss.insert(str[i][j]);
	 	 m[str[i][j]]=j;
	 	 num[str[i][j]]++;
	 }
}
for(int i=1;i<k+1;i++){
	 ok[1][i]=1;
}
mod=1e9+7;
set<string>::iterator itt;
for(int i=2;i<n+1;i++){
	 for(int j=1;j<k+1;j++){
	 	 x.clear();
	 	 for(int ii=0;ii<i-1;ii++){
	 	 	 x.push_back(str[i][j][ii]);
	     }
	 	 itt=ss.find(x);
	 	 if(itt!=ss.end()){
	 	 	 ok[i][j]+=(num[x]*ok[i-1][m[x]])%mod;
		 }
		 y.clear();
		 for(int ii=1;ii<i;ii++){
		 	 y.push_back(str[i][j][ii]);
		 }
		 itt=ss.find(y);
		 if(itt!=ss.end() and x!=y){
		 	 ok[i][j]+=(num[y]*ok[i-1][m[y]])%mod;
		 }
		 //cout<<str[i][j]<<ok[i][j]<<endl;
	 }
} 
for(int i=1;i<k+1;i++){
	 //cout<<okk<<endl;
	 okk=(okk+ok[n][i])%mod;
}
cout<<okk;
return 0;
}

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