#485760 (C++14) No.1060 素敵な宝箱

• 問題: No.1060 素敵な宝箱
• ユーザー: QCFium
• 提出日時: 2020-05-22 22:43:22
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,150 bytes
• コンパイル時間: 1,598 ms
• コンパイル使用メモリ: 167,896 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-04-15 17:51:06
• 合計ジャッジ時間: 2,917 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,944 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,944 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	WA	-
testcase_07	AC	2 ms; 6,940 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-

ソースコード

#include <bits/stdc++.h>

typedef uint32_t u32;
typedef uint64_t u64;
typedef int32_t s32;
typedef int64_t s64;

s32 ri() {
	s32 n;
	scanf("%" SCNd32, &n);
	return n;
}

#define INF 1000000000000000000

int main() {
#define int WHOOOO // 脱int訓練中につき許して
	s32 n = ri(), m = ri();
	s32 a[n][m];
	for (auto &i : a) for (auto &j : i) j = ri();
	
	s32 profit[n][n];
	for (s32 i = 0; i < n; i++) for (s32 j = 0; j < n; j++) {
		profit[i][j] = 0;
		for (s32 k = 0; k < m; k++) profit[i][j] += a[i][k] * a[j][k] * (1 + (i != j));
	}
	
	bool used[n];
	memset(used, 0, sizeof(used));
	s64 res[2] = { 0 };
	std::vector<s32> r0, r1;
	for (s32 i = 0; i < n; i++) {
		s64 plus[n];
		for (s32 j = 0; j < n; j++) {
			if (used[j]) {
				plus[j] = -INF;
				continue;
			}
			plus[j] = 0;
			// used[j] = true;
			for (s32 k = 0; k < n; k++) plus[j] += profit[j][k] * (1 + !used[k]);
			// used[j] = false;
		}
		auto &use = (i & 1) ? r1 : r0;
		s32 tmp = std::max_element(plus, plus + n) - plus;
		use.push_back(tmp);
		used[tmp] = true;
		for (auto k : use) res[i & 1] += profit[tmp][k];
	}
	printf("%" PRId64 "\n", res[0] - res[1]);
	return 0;
}