結果
問題 | No.2840 RGB Plates |
ユーザー | ococonomy1 |
提出日時 | 2024-08-09 22:33:08 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,754 bytes |
コンパイル時間 | 2,244 ms |
コンパイル使用メモリ | 216,692 KB |
実行使用メモリ | 61,952 KB |
最終ジャッジ日時 | 2024-08-09 22:33:12 |
合計ジャッジ時間 | 3,757 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 4 ms
6,940 KB |
testcase_04 | WA | - |
testcase_05 | AC | 3 ms
6,944 KB |
testcase_06 | AC | 4 ms
6,944 KB |
testcase_07 | AC | 5 ms
6,940 KB |
testcase_08 | AC | 13 ms
6,940 KB |
testcase_09 | AC | 63 ms
61,952 KB |
testcase_10 | AC | 4 ms
6,940 KB |
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 | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
ソースコード
//#pragma GCC target("avx2") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; using pli = pair<ll,int>; #define TEST cerr << "TEST" << endl #define AMARI 998244353 //#define AMARI 1000000007 #define el '\n' #define El '\n' #define MULTI_TEST_CASE false void solve(void){ //問題を見たらまず「この問題設定から言えること」をいっぱい言う //一個回答に繋がりそうな解法が見えても、実装や細かい詰めに時間がかかりそうなら別の方針を考えてみる //添え字回りで面倒になりそうなときは楽になる言い換えを実装の前にじっくり考える //ある程度考察しても全然取っ掛かりが見えないときは実験をしてみる //よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書く int n; cin >> n; vector<int> a(n); int sum = 0; for(int i = 0; i < n; i++){ cin >> a[i]; sum += a[i]; } sort(a.begin(),a.end()); if(n < 20){ map<int,int> mp; for(int S = 0; S < (1 << n); S++){ int temp = 0; for(int i = 0; i < n; i++){ if((S & (1 << i)))temp += a[i]; } mp[temp]++; } for(map<int,int>::iterator it = mp.begin(); it != mp.end(); it++){ if(it->second >= 2 && sum - it->first * 2 != 0){ cout << sum - it->first * 2 << el; return; } } cout << -1 << el; return; } map<int,int> mp; for(int S = 0; S < (1 << 16); S++){ int temp = 0; for(int i = 0; i < 16; i++){ if((S & (1 << i)))temp += a[i]; } mp[temp]++; } int m = -1; for(map<int,int>::iterator it = mp.begin(); it != mp.end(); it++){ if(it->second >= 2){ m = it->first; break; } } assert(m != -1); vector<vector<int>> dp(n + 1,vector<int>(m + 1,0)); dp[0][0] = 1; for(int i = 0; i < n; i++){ for(int j = 0; j <= m; j++){ dp[i + 1][j]++; if(j + a[i] <= m)dp[i + 1][j + a[i]]++; } } for(int i = 0; i <= m; i++){ if(dp[n][i] >= 2){ cout << sum - 2 * i << el; return; } } //assert(0); return; } void calc(void){ return; } signed main(void){ cin.tie(nullptr); ios::sync_with_stdio(false); calc(); int t = 1; if(MULTI_TEST_CASE)cin >> t; while(t--){ solve(); } return 0; }