Submission #5067729

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

typedef std::uint64_t u64;
typedef std::int64_t  i64;
typedef std::uint32_t u32;
typedef std::int32_t  i32;

using namespace std;

#define swap(a, b)    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while(0)
#define repd(i, a, b) for(typeof(b) i = a; i < (b); ++i)
#define rep(i, n)     repd(i, 0, n)
#define dump(x)       cerr << #x << " = " << (x) << endl
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl

int main(int argc, const char* argv[]) {
	u64 n;
	cin >> n;

	u64 t[n];
	u64 sum = 0;
	rep(i, n) {
		cin >> t[i];
		sum += t[i];
	}

	u64 m = 1 << n;
	u64 ret = 0xFFFFFFFFFFFFFFFF;
	repd(i, 1, m-1) {
		u64 tmp = 0;
		rep(j, n) {
			if( (i & (1 << j)) != 0) {
				tmp += t[i];
			}
		}
		tmp = max(tmp, sum - tmp);
		if(tmp < ret) {
			ret = tmp;
		}
	}
	cout << ret << endl;
	return 0;
}

Submission Info

Judge Result