比赛 国庆欢乐赛3 评测结果 ATTWWWWWWW
题目名称 Xor-Mul 棋盘 最终得分 10
用户昵称 LikableP 运行时间 8.269 s
代码语言 C++ 内存使用 4.83 MiB
提交时间 2025-10-05 11:37:22
显示代码纯文本
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ull;

template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T> T read(T& x) {
  return x = read<T>();
}

template <typename T, typename ...Others> void read(T& x, Others&... y) {
  read(x);
  read(y...);
}

template <typename T> void write(T x, char ed = '\n') {
  int sta[sizeof(T) << 2], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while(x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}

const int MAXN = 10;
const int MAXM = 10010;

struct EDGE {
  int u, v;
  ull c;
};

int n, m;
ull a[MAXN * MAXM], b[MAXN * MAXM], d[MAXN * MAXM], maxx, ans = 0x7fffffffffffffff;
vector<EDGE> edge;

#define tr(x, y) ((x - 1) * m + y)
void ParseIn() {
  read(n, m);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      maxx = max(maxx, read(a[tr(i ,j)]));
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      maxx = max(maxx, read(b[tr(i ,j)]));
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m - 1; ++j)
      edge.push_back({tr(i, j), tr(i, j + 1), read<ull>()});
  for (int i = 1; i <= n - 1; ++i)
    for (int j = 1; j <= m; ++j)
      edge.push_back({tr(i, j), tr(i + 1, j), read<ull>()});
  for (int i = 1; i <= m; ++i)
    edge.push_back({tr(1, i), tr(n, i), read<ull>()});
}

void calc() {
  ull comp = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      comp += (d[tr(i, j)] ^ a[tr(i, j)]) * b[tr(i, j)];
    }
  }
  for (EDGE e : edge) {
    comp += (d[e.u] ^ d[e.v]) * e.c;
  }
  ans = min(ans, comp);
}

void dfs(int step) {
  if (step > n * m) {
    calc();
    return ;
  }
  for (ull i = 0; i <= maxx; ++i) {
    d[step] = i;
    dfs(step + 1);
  }
}

void Huhh() {
  ans = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      d[tr(i, j)] = ~a[tr(i ,j)];
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      ans += (d[tr(i, j)] ^ a[tr(i, j)]) * b[tr(i, j)];
    }
  }
  for (EDGE e : edge) {
    ans += (d[e.u] ^ d[e.v]) * e.c;
  }
  write(ans);
}

int main() {
  freopen("chessboardd.in", "r", stdin);
  freopen("chessboardd.out", "w", stdout);
  ParseIn();
  if (m <= 100) {
    dfs(1);
    write(ans);
  } else {
    Huhh();
  }
  return 0;
}