結果

問題 No.2840 RGB Plates
コンテスト
ユーザー vjudge1
提出日時 2025-08-10 21:47:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 371 ms / 2,000 ms
コード長 1,048 bytes
コンパイル時間 3,200 ms
コンパイル使用メモリ 278,784 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-10 21:47:38
合計ジャッジ時間 10,714 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Copyright (c) 2025 hanziwei
// All rights reserved

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

using i128 = __int128;
using u128 = unsigned __int128;

constexpr int inf = 1 << 27;
constexpr int dlt = 30000;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int32_t main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int N;
	std::cin >> N;

	std::vector <int> A(N);
	for (int i = 0; i < N; i++) {
		std::cin >> A[i];
	}
	
	std::vector <int> f(2 * dlt + 1, inf);
	for (int i = 0; i < N; i++) {
		auto g = f;
		for (int j = 0; j <= 2 * dlt; j++) {
			if (j - A[i] >= 0) { g[j - A[i]] = std::min(g[j - A[i]], (j == dlt ? 0 : f[j]) + A[i]); }
			if (j + A[i] <= 2 * dlt) { g[j + A[i]] = std::min(g[j + A[i]], (j == dlt ? 0 : f[j]) + A[i]); }
		}
		f = std::move(g);
	}

	int sumA = 0;
	for (int i = 0; i < N; i++) {
		sumA += A[i];
	}

	if (f[dlt] >= sumA) {
		std::cout << "-1\n";
	} else {
		std::cout << sumA - f[dlt] << "\n";
	}

	return 0;
}
0