結果

問題 No.2918 Divide Applicants Fairly
ユーザー clever-elsieclever-elsie
提出日時 2024-10-07 21:37:01
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 3,498 bytes
コンパイル時間 3,715 ms
コンパイル使用メモリ 290,880 KB
実行使用メモリ 813,824 KB
最終ジャッジ日時 2024-10-07 21:37:10
合計ジャッジ時間 8,020 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 21 ms
10,752 KB
testcase_04 AC 14 ms
8,192 KB
testcase_05 AC 5 ms
6,816 KB
testcase_06 AC 32 ms
14,976 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 52 ms
20,480 KB
testcase_10 AC 31 ms
14,592 KB
testcase_11 AC 278 ms
77,952 KB
testcase_12 MLE -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
testcase_58 -- -
testcase_59 -- -
testcase_60 -- -
testcase_61 -- -
testcase_62 -- -
testcase_63 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define _TP template
#define _CT const
#define _CC constexpr
#define _US using
_US namespace std;
namespace vies = std::views;
_US std::cin;
_US std::cout;
_US sstream = stringstream;
#define fi first
#define se second
#define endl '\n'
#define sn(i, c) " \n"[i == c];
#define pf(a) push_front(a)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define ppf() pop_front()
#define ppb() pop_back()
#define pp() pop()
#define ins(a) insert(a)
#define emp(a) emplace(a)
#define mp(f, s) make_pair(f, s)
#define A(a) begin(a), end(a)
#define I(a, i) begin(a), begin(a) + i
_TP<class f> _US vc = vector<f>;
_TP<class f> _US vv = vc<vc<f>>;
_TP<class f> _US v3 = vv<vc<f>>;
_TP<class f> _US v4 = vv<vv<f>>;
_TP<class f> _US gr = greater<f>;
_TP<class f> _US pq = priority_queue<f>;
_TP<class f> _US pqg = priority_queue<f, vc<f>, gr<f>>;
#define int int64_t
#define itn int64_t
#define uset unordered_set
#define umap unordered_map
_US i8 = int8_t;
_US u8 = uint8_t;
_US i16 = int16_t;
_US u16 = uint16_t;
_US i32 = int32_t;
_US u32 = uint32_t;
_US i64 = int64_t;
_US u64 = uint64_t;
_US intw = __int128_t;
_US uintw = __uint128_t;
_US f32 = float;
_US f64 = double;
_US vi = vc<int>;
_US vb = vc<bool>;
_US pi = pair<int, int>;
_US str = string;
_US vs = vc<str>;
_US VI = vv<int>;
_US VB = vv<bool>;
_US pqgp = pqg<pi>;
_CC str yes{"Yes\n"};
_CC str no{"No\n"};
_CC int inf = 1ll << 60;
_CC int minf = -inf;
_CC array<pi, 8> dc = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}};
_CC array<unsigned, 6> mods{998244353,	998244853, 1000000007, 1000000009, 1000000021, 1000000033};
inline int ceil(_CT int a, const int b) { return (a + b - 1) / b; }
inline int floor(const int a, const int b) { return a / b - (a % b && (a ^ b) < 0); }

#define UINT unsigned_integral
#define SINT signed_integral
#define MUT make_unsigned_t
#define PPCNT popcount
#define MSB countl_zero
#define LSB countr_zero
_TP<UINT T> int pcnt(T p){ return PPCNT(p); }
_TP<SINT T> int pcnt(T p){ return PPCNT(MUT<T>(p)); }
_TP<UINT T> int zcnt(T p){ return MSB(p); }
_TP<SINT T> int zcnt(T p){ return MSB(MUT<T>(p)); }
_TP<UINT T> int lsb(T p){ return LSB(p); }
_TP<SINT T> int lsb(T p){ return LSB(MUT<T>(p)); }



void IOset(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(15);
}

signed main() {
	IOset();
	int n;cin>>n;
	vi a(n);for(int&x:a)cin>>x;
	int ans=inf;
	for(int i=0;i<n-1;i++)
	for(int j=i+1;j<n;j++)
		ans=min(ans,abs(a[i]-a[j]));
	multimap<int,set<int>>b;
	for(int j=0;j<n;j++)b.ins(mp(a[j],set<int>({j})));
	for(int i=2;i*2<=n;i++){
		auto old=move(b);
		b.clear();
		auto itr=old.rbegin();
		for(;itr!=old.rend();itr++){
			for(int j=0;j<n;j++){
				if(!itr->se.contains(j)){
					set<int>tmp=itr->se;
					tmp.ins(j);
					b.ins(mp(itr->fi+a[j],move(tmp)));
				}
			}
		}
		for(auto itr=b.begin();itr!=b.end();){
			auto next=b.upper_bound(itr->fi);
			auto jtr=itr;
			for(jtr++;jtr!=next;jtr++){
				bool out=true;
				for(auto const&x:itr->se){
					if(jtr->se.contains(x)){
						out =false;
						break;
					}
				}
				if(out){
					ans=0;
					cout<<0<<endl;
					return 0;
				}
			}
			if(next==b.end())break;
			auto nnext=b.upper_bound(next->fi);
			jtr=next;
			for(jtr++;jtr!=nnext;jtr++){
				bool out=true;
				for(auto const&x:itr->se){
					if(jtr->se.contains(x)){
						out =false;
						break;
					}
				}
				if(out) ans=min(ans,jtr->fi-itr->fi);
			}
			itr=next;
		}
	}
	cout<<ans<<endl;
}
0