結果

問題 No.2918 Divide Applicants Fairly
ユーザー miie
提出日時 2024-10-08 22:13:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 858 bytes
コンパイル時間 3,535 ms
コンパイル使用メモリ 252,708 KB
実行使用メモリ 51,328 KB
最終ジャッジ日時 2024-10-08 22:13:56
合計ジャッジ時間 6,979 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 20 WA * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	vector<int> x(n);
	for(int i=0; i<n; i++){
		cin >> x[i];
	}
	vector<set<int>> a(n), b(n);
	int mid = n/2;
	for(int i=0; i<(1<<mid); i++){
		int cnt = 0;
		int score = 0;
		for(int j=0; j<mid; j++){
			if(i&(1<<j)){
				cnt++;
				score += x[j];
			}
			else{
				score -= x[j];
			}
		}
		a[cnt].insert(score);
	}
	for(int i=0; i<(1<<mid); i++){
		int cnt = 0;
		int score = 0;
		for(int j=mid; j<n; j++){
			if(i&(1<<j-mid)){
				cnt++;
				score += x[j];
			}
			else{
				score -= x[j];
			}
		}
		b[cnt].insert(score);
	}
	int ans = 1e9;
	for(int i=0; i<=mid; i++){
		for(int xx : a[i]){
			auto itr = b[mid-i].lower_bound(-xx);
			if(itr != b[mid-i].end()) ans = min(ans, xx+*itr);
			if(itr != b[mid-i].begin()) ans = min(ans, -xx-*prev(itr));
		}
	}
	cout << ans << endl;
}
0