結果

問題 No.1060 素敵な宝箱
ユーザー QCFium
提出日時 2020-05-22 22:13:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,143 bytes
コンパイル時間 1,790 ms
コンパイル使用メモリ 170,884 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-05 17:57:12
合計ジャッジ時間 2,883 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:29:15: warning: 'void* memset(void*, int, size_t)' specified size between 18446744071562067968 and 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   29 |         memset(used, 0, sizeof(used));
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#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;
}
0