Submission #1339439

#TimeUsernameProblemLanguageResultExecution timeMemory
1339439po_rag526Parametriziran (COCI19_parametriziran)C++20
110 / 110
153 ms2980 KiB
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int MAXN = 5e4;
const int MAXM = 6;
const int SIGMA = 26;

std::bitset<MAXN> who[6][SIGMA + 1];
std::bitset<MAXN> cand;
std::bitset<MAXN> all;

int main() {
  int n, m;
  std::cin >> n >> m;

  std::vector<std::string> s(n);

  for (int i = 0; i < n; i++) {
		std::cin >> s[i];
    for (char &c : s[i]) {
      if (c == '?') {
        c = 0;
      } else {
        c -= 'a';
        c++;
      }
    }
    for (int j = 0; j < m; j++) {
      who[j][s[i][j]][i] = true;
      if (s[i][j] == 0) {
				for (int k = 1; k <= 26; k++) {
					who[j][k][i] = true;
				}
      }
    }
  }

	for (int i = 0; i < n; i++) {
		all[i] = true;
	}

	ll answer = 0;

  for (int i = 0; i < n; i++) {
		cand = all;
		for (int j = 0; j < m; j++) {
			if (s[i][j] != 0) {
			  cand &= who[j][s[i][j]];
			}
		}
		answer += cand.count();
  }

  answer -= n;

  std::cout << answer / 2;

  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...