Submission #1339436

#TimeUsernameProblemLanguageResultExecution timeMemory
1339436po_rag526Parametriziran (COCI19_parametriziran)C++20
110 / 110
199 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;
    }
  }

	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]] | who[j][0];
			}
		}
//		for (int j = 0; j < n; j++) {
//			std::cout << cand[j];
//		}
//		std::cout << '\n';
		answer += cand.count();
  }

  answer -= n;

  std::cout << answer / 2;

  return 0;
}
// a treia oara e cu noroc
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...