oj.uz

Submission #445089

# Submission time Handle Problem Language Result Execution time Memory
445089 2021-07-16T11:36:09 Z Tahmid690 Trener (COCI20_trener) C++14
110 / 110
 1302 ms 34180 KB 
// "Say:He is the Most Merciful,We have believed in him and upon him we have relied" [67:29]
 
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
//#pragma GCC optimize("unroll-loops")
 
#include<bits/stdc++.h>
using namespace std;
                                                     
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 */
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef map<int,int> mpi;
typedef map<ll,ll> mpl;
typedef unordered_map<int,int> umpi;
typedef unordered_map<ll,ll> umpl;
 
#define ump unordered_map
#define mod 1000000007
#define inf 1000000000000000006
#define infi 1000000009
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
#define pi acos(-1.0)
#define dec(n) fixed << setprecision(n)
#define N 200005
//#define int long long



struct ss{
	ll hash[55];
};
ll bigmod(ll a,ll b){
    if(b==0) return 1;
    ll ret=bigmod(a,b/2);
    ret*=ret;
    ret%=mod;
    if(b%2==1) ret*=a;
    return ret%mod;
    
}

vector<ss> v[55];
string s;
int n,k;
ll dp[1505][55],inv;
ll DP(int p,int x){
	if(x==n) return 1;
	if(dp[p][x]!=-1) return dp[p][x];
	ll ret=0;
	for(int i=0;i<k;i++){
		if(v[x][i].hash[x]==v[x-1][p].hash[x] || ((((v[x][i].hash[x+1]-v[x][i].hash[1])*inv)+mod)%mod)==v[x-1][p].hash[x]) ret+=DP(i,x+1);
		ret%=mod;
	}
	return dp[p][x]=ret;
}
void solve(){
	cin >> n >> k;
	for(int i=0;i<n;i++){
		v[i].resize(k);
		for(int j=0;j<k;j++){
			cin >> s;
			ss tmp;
			ll p=31,hashval=0,pw=1;
		    for(int k=0;k<s.size();k++){
        		hashval=(hashval+(s[k]-'a'+1)*pw)%mod;
        		pw=(pw*p)%mod;
        		tmp.hash[k+1]=hashval;
    		}
			v[i][j]=tmp;
		}
	}
	inv=bigmod(31,mod-2);
	memset(dp,-1,sizeof dp);
	ll ans=0;
	for(int i=0;i<k;i++){
		ans+=DP(i,1);
		ans%=mod;
	}
	cout << ans << endl;
	
}

signed main(){
    fastio;
    //srand(chrono::steady_clock::now().time_since_epoch().count());
    int T=1,cs=0;
    //cin >> T;
    while(T--){
        //cout << "Case " << ++cs << ":" << " " ; 
    	solve();
    } 
}

Compilation message

trener.cpp: In function 'void solve()':
trener.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |       for(int k=0;k<s.size();k++){
      |                   ~^~~~~~~~~
trener.cpp: In function 'int main()':
trener.cpp:103:13: warning: unused variable 'cs' [-Wunused-variable]
  103 |     int T=1,cs=0;
      |             ^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 956 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3148 KB Output is correct
2 Correct 8 ms 3148 KB Output is correct
3 Correct 7 ms 3148 KB Output is correct
4 Correct 14 ms 3244 KB Output is correct
5 Correct 7 ms 3148 KB Output is correct
6 Correct 9 ms 3148 KB Output is correct
7 Correct 8 ms 3236 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 956 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 6 ms 3148 KB Output is correct
6 Correct 8 ms 3148 KB Output is correct
7 Correct 7 ms 3148 KB Output is correct
8 Correct 14 ms 3244 KB Output is correct
9 Correct 7 ms 3148 KB Output is correct
10 Correct 9 ms 3148 KB Output is correct
11 Correct 8 ms 3236 KB Output is correct
12 Correct 1302 ms 33708 KB Output is correct
13 Correct 1143 ms 34060 KB Output is correct
14 Correct 1155 ms 34060 KB Output is correct
15 Correct 1196 ms 34116 KB Output is correct
16 Correct 861 ms 34180 KB Output is correct
17 Correct 1215 ms 34116 KB Output is correct
18 Correct 1087 ms 34120 KB Output is correct
19 Correct 1078 ms 33992 KB Output is correct
20 Correct 1096 ms 34116 KB Output is correct
21 Correct 1108 ms 34112 KB Output is correct
22 Correct 859 ms 34116 KB Output is correct