oj.uz

Submission #445082

# Submission time Handle Problem Language Result Execution time Memory
445082 2021-07-16T11:24:57 Z Tahmid690 Trener (COCI20_trener) C++14
55 / 110
 2000 ms 6316 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

vector<string> v[55];

int n,k;
ll dp[1505][55];
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].substr(0,x)==v[x-1][p] || v[x][i].substr(1,x)==v[x-1][p]) 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 >> v[i][j];
	}
	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 'int main()':
trener.cpp:77:13: warning: unused variable 'cs' [-Wunused-variable]
   77 |     int T=1,cs=0;
      |             ^~

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1356 KB Output is correct
2 Correct 35 ms 1356 KB Output is correct
3 Correct 34 ms 1364 KB Output is correct
4 Correct 21 ms 1440 KB Output is correct
5 Correct 34 ms 1428 KB Output is correct
6 Correct 37 ms 1420 KB Output is correct
7 Correct 23 ms 1356 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 34 ms 1356 KB Output is correct
6 Correct 35 ms 1356 KB Output is correct
7 Correct 34 ms 1364 KB Output is correct
8 Correct 21 ms 1440 KB Output is correct
9 Correct 34 ms 1428 KB Output is correct
10 Correct 37 ms 1420 KB Output is correct
11 Correct 23 ms 1356 KB Output is correct
12 Execution timed out 2071 ms 6316 KB Time limit exceeded
13 Halted 0 ms 0 KB -