Submission #445153

#	Time	Username	Problem	Language	Result	Execution time	Memory
445153		Wasif_Jamil	Trener (COCI20_trener)	C++14	55 / 110	2072 ms	6860 KiB

trener

// "Say:He is the Most Merciful,We have believed in him and upon him we have relied" [67:29]
 
#include<bits/stdc++.h>
using namespace std; 
const int mod = 1e9 + 7;

bool is(string a, string b){
    char x = a.back();
    a.pop_back();
    if(a == b){
        return 1;
    }
    a.push_back(x);
    a.erase(a.begin());
    if(a == b){
        return 1;
    }
    return 0;
}

void add_self(int &a, int b){
    a += b;
    if(a >= mod){
        a -= mod;
    }
}

int main(){
    int n, m; cin >> n >> m;
    vector<vector<string>>v(n+1, vector<string>(m+1));
    vector<vector<int>>dp(n+1, vector<int>(m+1));
    for(int i=1;i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> v[i][j];
            if(i == n){
                dp[i][j] = 1;
            }
        }
    }
    for(int i=n-1; i>=1; i--){
        for(int j=1; j<=m; j++){
            for(int x=1; x<=m; x++){
                if(is(v[i+1][x], v[i][j])){
                    add_self(dp[i][j], dp[i+1][x]);
                } 
            }
        }
    }
    int sum = 0;
    for(int i=1; i<=m; i++){
        add_self(sum, dp[1][i]);
    }
    cout << sum << "\n";
    return 0;
}

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