Submission #1339486

#TimeUsernameProblemLanguageResultExecution timeMemory
1339486po_rag526Parametriziran (COCI19_parametriziran)C++17
110 / 110
622 ms5196 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 1e5;
const int MOD = 666013;

bitset<MAXN + 1> has[6][27];
string s1[MAXN + 1];

signed main() {
    int n, m, i, j;
    long long ans = 0;
    string s;

    cin >> n >> m;

    for (i = 1; i <= n; i++) {
        cin >> s1[i];
        for (j = 0; j < m; j++) {
            if (s1[i][j] != '?')
                s1[i][j] -= 'a';
            else
                s1[i][j] = 26;

            has[j][(int)s1[i][j]][i] = 1;
        }
    }

    bitset<MAXN + 1> aux, correct;
    aux.set();
    //correct.set();
    for (i = 1; i <= n; i++) {
        bool ok = 1;
        correct = aux;
        s = s1[i];
        for (j = 0; j < m; j++) {
            if (s[j] != 26) {
                correct &= (has[j][(int)s[j]]|has[j][26]);
                ok = 0;
            }
        }

        if (ok == 1)
            ans += n;
        else
            ans += correct.count();
        //aux = correct;
    }
    ans -= n;
    ans /= 2;
    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...