Submission #845343

#	Time	Username	Problem	Language	Result	Execution time	Memory
845343		vjudge1	Trener (COCI20_trener)	C++17	55 / 110	2044 ms	416 KiB

trener

#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;
}

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