#188890 (C++14) No.545 ママの大事な二人の子供

• 問題: No.545 ママの大事な二人の子供
• ユーザー: gzlcp
• 提出日時: 2017-07-14 22:58:42
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 67 ms / 2,000 ms
• コード長: 2,287 bytes
• コンパイル時間: 1,182 ms
• コンパイル使用メモリ: 94,872 KB
• 実行使用メモリ: 10,496 KB
• 最終ジャッジ日時: 2024-10-07 23:46:53
• 合計ジャッジ時間: 2,790 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
other	AC * 32

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define REP(i, n) for(long long i = 0; i < n; ++i)
#define ALL(a) a.begin(), a.end()
#define INF (long long)1000000000
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int main() {
    int n;
    cin>>n;
    vector<P> a(n);
    REP(i, n) cin>>a[i].first>>a[i].second;
    int half = n/2;
    set<ll> aover1;
    set<ll> bover1;
    set<ll> aover2;
    set<ll> bover2;
    for(ll bit = 0; bit < (1<<half); ++bit) {
        ll asum = 0, bsum = 0;
        REP(i, half) {
            if((bit>>i)&1) asum += a[i].first;
            else bsum += a[i].second;
        }
        if(asum >= bsum) aover1.insert(asum - bsum);
        if(asum <= bsum) bover1.insert(bsum - asum);
    }
    for(ll bit = 0; bit < (1<<(n - half)); ++bit) {
        ll asum = 0, bsum = 0;
        REP(i, n - half) {
            if((bit>>i)&1) asum += a[half + i].first;
            else bsum += a[half + i].second;
        }
        if(asum >= bsum) aover2.insert(asum - bsum);
        if(asum <= bsum) bover2.insert(bsum - asum);
    }
    ll res = INF * INF;
    if(aover1.size() > 0 && aover2.size() > 0) res = min(res, *(aover1.begin()) + *(aover2.begin()));
    if(bover1.size() > 0 && bover2.size() > 0) res = min(res, *(bover1.begin()) + *(bover2.begin()));
    vector<ll> ao1(aover1.size());
    vector<ll> ao2(aover2.size());
    vector<ll> bo1(bover1.size());
    vector<ll> bo2(bover2.size());
    auto ite = aover1.begin();
    int roc = 0;
    while(ite != aover1.end()) {
        ao1[roc] = *ite;
        ++ite;
        ++roc;
    }
    ite = aover2.begin();
    roc = 0;
    while(ite != aover2.end()) {
        ao2[roc] = *ite;
        ++ite;
        ++roc;
    }
    ite = bover1.begin();
    roc = 0;
    while(ite != bover1.end()) {
        bo1[roc] = *ite;
        ++ite;
        ++roc;
    }
    ite = bover2.begin();
    roc = 0;
    while(ite != bover2.end()) {
        bo2[roc] = *ite;
        ++ite;
        ++roc;
    }
    roc = 0;
    while(roc < ao1.size()) {
        auto ite1 = lower_bound(ALL(bo2), ao1[roc]);
        if(ite1 != bo2.end()) {
            res = min(res, abs(ao1[roc] - *ite1));
        }
        if(ite1 != bo2.begin()) {
            res = min(res, abs(ao1[roc] - *(--ite1)));
        }
        ++roc;
    }
    roc = 0;
    while(roc < bo1.size()) {
        auto ite2 = lower_bound(ALL(ao2), bo1[roc]);
        if(ite2 != ao2.end()) {
            res = min(res, abs(bo1[roc] - *ite2));
        }
        if(ite2 != ao2.begin()) {
            res = min(res, abs(bo1[roc] - *(--ite2)));
        }
        ++roc;
    }
    cout<<res<<endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX