結果
問題 | No.2840 RGB Plates |
ユーザー |
👑 ![]() |
提出日時 | 2024-08-09 22:04:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,846 ms / 2,000 ms |
コード長 | 1,623 bytes |
コンパイル時間 | 1,900 ms |
コンパイル使用メモリ | 107,428 KB |
最終ジャッジ日時 | 2025-02-23 21:37:06 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include <iostream> #include <string> #include <vector> #include <algorithm> using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<int(n); i++) const i64 INF = 1001001001001001001; template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; } template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; } #include <atcoder/modint> #include <bitset> #include <type_traits> namespace nachia{ template<class TargetInt, TargetInt Max, TargetInt Min = TargetInt(1), class Callback> void CallWithConstexprFittingInt(TargetInt val, const Callback& callback){ if(Max / 2 < val || Max / 2 < Min){ callback(std::integral_constant<TargetInt, Max>()); return; } CallWithConstexprFittingInt<TargetInt, Max / 2, Min, Callback>(val, callback); } } using Modint = atcoder::static_modint<998244353>; using namespace std; void testcase(){ int N; cin >> N; vector<int> A(N); rep(i,N) cin >> A[i]; int Z = 0; for(auto a : A) Z += a; int ans = -1; nachia::CallWithConstexprFittingInt<int, 1<<23>(Z/2+1, [&](auto X){ constexpr int x = X.value; using Set = bitset<x>; Set dp; Set res; dp.set(0); for(int a : A){ Set nx = dp; nx <<= a; res |= nx & dp; dp |= nx; } for(int i=0; i<x; i++) if(res.test(i)){ ans = Z - i * 2; break; } }); if(ans <= 0) ans = -1; cout << ans << '\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }