Submission #445177

#	Time	Username	Problem	Language	Result	Execution time	Memory
445177		Wasif_Jamil	Trener (COCI20_trener)	C++14	110 / 110	650 ms	159556 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;

map<deque<char>, vector<int>>mp;


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

int main(){
    int n, m; cin >> n >> m;
    vector< vector<deque<char> > >v(n+1, vector<deque<char>>(m+1));
    vector<vector<int>>dp(n+1, vector<int>(m+1));
    vector< vector<bool> >flag(n+1, vector<bool>(m+1));
    for(int i=1;i<=n; i++){
        for(int j=1; j<=m; j++){
            for(int x=1; x<=i; x++){
                char val; cin >> val;
                v[i][j].push_back(val);
            }
            if(count(v[i][j].begin(), v[i][j].end(), v[i][j][0]) == (int)v[i][j].size()){
                flag[i][j] = 1;
            }
            mp[v[i][j]].push_back(j);
            if(i == n){
                dp[i][j] = 1;
            }
        }
    }
    for(int i=n; i>=2; i--){
        for(int x=1; x<=m; x++){
            char val = v[i][x].back();
            v[i][x].pop_back();
            for(int e:mp[v[i][x]]){
                add_self(dp[i-1][e], dp[i][x]);
            }
            v[i][x].push_back(val);
            if(flag[i][x]){
                continue;
            }
            val = v[i][x].front();
            v[i][x].pop_front();
            for(int e:mp[v[i][x]]){
                add_self(dp[i-1][e], dp[i][x]);
            }
            v[i][x].push_front(val);
        }
    }
    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: 55 / 55