結果

問題 No.2918 Divide Applicants Fairly
ユーザー clever-elsie
提出日時 2024-10-07 21:37:01
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 MLE * 1 -- * 51
権限があれば一括ダウンロードができます

ソースコード

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