結果

問題 No.2918 Divide Applicants Fairly
ユーザー けいと
提出日時 2024-10-09 01:05:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,427 bytes
コンパイル時間 3,813 ms
コンパイル使用メモリ 284,940 KB
実行使用メモリ 814,688 KB
最終ジャッジ日時 2024-10-09 01:06:01
合計ジャッジ時間 6,184 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other MLE * 1 -- * 60
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<ll> r(n);
    for(auto &x : r) cin >> x;
    
    int n1 = n / 2;
    int n2 = n - n1;
    vector<ll> first_half(r.begin(), r.begin() + n1);
    vector<ll> second_half(r.begin() + n1, r.end());
    
    auto generate_subset_sums = [&](const vector<ll> &arr) -> vector<ll> {
        vector<ll> sums = {0};
        for(auto num : arr){
            int sz = sums.size();
            for(int i =0; i < sz; ++i){
                sums.push_back(sums[i] + num);
            }
        }
        return sums;
    };
    
    vector<ll> sums1 = generate_subset_sums(first_half);
    vector<ll> sums2 = generate_subset_sums(second_half);
    
    sort(sums1.begin(), sums1.end());
    sort(sums2.begin(), sums2.end());
    
    vector<ll> all_sums;
    all_sums.reserve(sums1.size() + sums2.size());
    for(auto s1 : sums1){
        for(auto s2 : sums2){
            all_sums.push_back(s1 + s2);
        }
    }
    
    sort(all_sums.begin(), all_sums.end());
    
    ll min_diff = LLONG_MAX;
    for(int i =1; i < all_sums.size(); ++i){
        ll diff = all_sums[i] - all_sums[i-1];
        if(diff < min_diff){
            min_diff = diff;
            if(min_diff ==1){
                break;
            }
        }
    }
    
    cout << min_diff << "\n";
}
0