結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | 0x19f |
提出日時 | 2017-07-15 18:28:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 943 bytes |
コンパイル時間 | 849 ms |
コンパイル使用メモリ | 76,960 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-08 02:32:46 |
合計ジャッジ時間 | 2,114 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)#define INF (1LL << 60)using namespace std;typedef long long ll;ll N;vector<ll> A[2], B[2];int main(void) {cin >> N;REP(i, 0, N) {ll a, b;cin >> a >> b;A[i % 2].push_back(a);B[i % 2].push_back(b);}if(N == 1) cout << min(abs(A[0][0]), B[0][0]) << endl;else {vector<ll> v[2];REP(g, 0, 2) {REP(i, 0, 1 << A[g].size()) {ll s = 0;REP(j, 0, A[g].size()) s += (i & (1 << j)) ? A[g][j] : -B[g][j];v[g].push_back(s);}sort(v[g].begin(), v[g].end());}ll ans = INF;REP(i, 0, v[0].size()) {int d = upper_bound(v[1].begin(), v[1].end(), -v[0][i]) - v[1].begin();ans = min(ans, abs(v[0][i] + v[1][d]));if(d - 1 >= 0) ans = min(ans, abs(v[0][i] + v[1][d - 1]));}cout << ans << endl;}}