Submission #845343

#TimeUsernameProblemLanguageResultExecution timeMemory
845343vjudge1Trener (COCI20_trener)C++17
55 / 110
2044 ms416 KiB
#include <iostream>
#include <algorithm>
using namespace std;


int main(){
    int n, k;
    bool isvalid;
    int64_t mod = 1000000007, *scores, *newscores, *codes, *newcodes, pow26 = 1;
    string surname, newsurname;
    cin >> n >> k;
    scores = new int64_t[k];
    newscores = new int64_t[k];
    codes = new int64_t[k];
    newcodes = new int64_t[k];
    for (int i = 0; i < k; i++){
        cin >> surname;
        codes[i] = surname[0] - 'a';
        scores[i] = 1;
    }
    for (int newlen = 2; newlen <= n; newlen++){
        pow26 = (pow26 * 26) % mod;
        for (int i = 0; i < k; i++){
            cin >> newsurname;
            newscores[i] = 0;
            newcodes[i] = 0;
            for (int letter = 0; letter < newlen; letter++){
                newcodes[i] = (newcodes[i] * 26 + (newsurname[letter] - 'a')) % mod;
            }
            for (int j = 0; j < k; j++){
                isvalid = false;
                for (int newletter = 0; newletter < 26; newletter++){
                    if ((codes[j] * 26 + newletter) % mod == newcodes[i]){
                        isvalid = true;
                        break;
                    }
                    if ((codes[j] + pow26 * newletter) % mod == newcodes[i]){
                        isvalid = true;
                        break;
                    }
                }
                if (isvalid) newscores[i] = (newscores[i] + scores[j]) % mod;
            }
        }
        for (int i = 0; i < k; i++){
            codes[i] = newcodes[i];
            scores[i] = newscores[i];
        }
    }
    int64_t total = 0;
    for (int i = 0; i < k; i++){
        total = (total + scores[i]) % mod;
    }
    cout << total;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...