Submission #401663

#	Time	Username	Problem	Language	Result	Execution time	Memory
401663		eblabrada	Bank (IZhO14_bank)	C++17	100 / 100	112 ms	4444 KiB

bank

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

using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

template<class T> using V = vector<T>;
template<class T> using PR = pair<T,T>;
template<class T, size_t SZ> using AR = array<T,SZ>;
template<class T> using pqg = priority_queue<T,V<T>,greater<T>>;

// pairs
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(x) (int)((x).size())
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define each(a,x) for (auto& a: x)

const int MX  = 2e5+5;
const int MOD = 1e9+7; // 998244353;
const ll  INF = 1e18; // not too close to LLONG_MAX
const db  PI  = acos((db)-1);
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; // for every grid problem!!

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

// bitwise ops
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { // make C++11 compatible until USACO updates ...
	return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))

template<class T> T cdiv(T a, T b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
template<class T> T fdiv(T a, T b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

template<class T> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
template<class T> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; } // set a = max(a,b)

template<class T, class U> T fstTrue(T lo, T hi, U f) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1;
	}
	return lo;
}
template<class T, class U> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	}
	return lo;
}

inline namespace Helpers {
	// is_iterable
	template<class T, class = void> struct is_iterable : false_type {};
	template<class T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
	    decltype(end(declval<T>()))>> : true_type {};
	template<class T> constexpr bool is_iterable_v = is_iterable<T>::value;

	// is_printable
	template<class T, class = void> struct is_printable : false_type {};
	template<class T> struct is_printable<T, typename std::enable_if_t<is_same_v
		<decltype(cout << declval<T>()), ostream&>>> : true_type {};
	template<class T> constexpr bool is_printable_v = is_printable<T>::value;
}

inline namespace ToString {
	template<class T> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;

	// ts: string representation to print
	template<class T> typename enable_if<is_printable_v<T>,str>::type ts(T v) {
		stringstream ss; ss << fixed << setprecision(15) << v;
		return ss.str(); } // default
	template<class T> str bit_vec(T t) { // bit vector to string
		str res = "{"; F0R(i,sz(t)) res += ts(t[i]);
		res += "}"; return res; }
	str ts(V<bool> v) { return bit_vec(v); }
	template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); } // bit vector
	template<class T, class U> str ts(pair<T,U> p); // pairs
	template<class T> typename enable_if<needs_output_v<T>,str>::type ts(T v); // vectors, arrays
	template<class T, class U> str ts(pair<T,U> p) { return "("+ts(p.f)+", "+ts(p.s)+")"; }
	template<class T> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep) {
		// convert container to string w/ separator sep
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += sep;
			fst = 0; res += ts(x);
		}
		return res;
	}
	template<class T> typename enable_if<needs_output_v<T>,str>::type ts(T v) {
		return "{"+ts_sep(v,", ")+"}"; }

	// for nested DS
	template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type
	  ts_lev(const T& v) { return {ts(v)}; }
	template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type
	  ts_lev(const T& v) {
		if (lev == 0 || !sz(v)) return {ts(v)};
		vs res;
		for (const auto& t: v) {
			if (sz(res)) res.bk += ",";
			vs tmp = ts_lev<lev-1>(t);
			res.ins(end(res),all(tmp));
		}
		F0R(i,sz(res)) {
			str bef = " "; if (i == 0) bef = "{";
			res[i] = bef+res[i];
		}
		res.bk += "}";
		return res;
	}
}

inline namespace Debug {
	void dbg_out() { cerr << "]" << endl; }
	template<class T, class ...U> void dbg_out(const T& t, const U&... u) {
		cerr << ts(t); if (sizeof...(u)) cerr << ", ";
		dbg_out(u...); }
	#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
		#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", dbg_out(__VA_ARGS__)
		#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
			<< __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
	#else // don't actually submit with this
		#define dbg(...) 0
		#define chk(...) 0
	#endif
}

inline namespace FileIO {
	void setPrec() { cout << fixed << setprecision(15); }
	void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
	void setIn(str S)  { freopen(S.c_str(),"r",stdin); }
	void setOut(str S) { freopen(S.c_str(),"w",stdout); }
	void setIO(str S = "") {
		unsyncIO(); setPrec();
		// cin.exceptions(cin.failbit);
		// throws exception when do smth illegal
		// ex. try to read letter into int
		if (sz(S)) setIn(S+".in"), setOut(S+".out"); // for old USACO
	}
}

int32_t main() {
	setIO();

	int N,M; cin >> N >> M;

	vi A(N); each(x,A) cin >> x;
	vi B(M); each(x,B) cin >> x;

	vi prefix(N);
	F0R(i,N) {
		prefix[i] = A[i];
		if (i) prefix[i] += prefix[i-1];
	}

	vi dp(1<<M); dp[0] = 1;
	F0R(mask,1<<M) if (dp[mask]) {
		int sum = 0;
		F0R(i,M) if ((mask>>i)&1)
			sum += B[i];
		
		int ind = 0;
		while(ind < N && sum >= prefix[ind])
			ind++;
			
		if (ind == N) {
			cout << "YES\n";
			return 0;
		}

		F0R(i,M) if ((mask>>i)^1 && sum+B[i] <= prefix[ind])
			dp[mask|(1<<i)] = 1;
	}

	cout << "NO\n";

}

Compilation message (stderr)

bank.cpp: In function 'void FileIO::setIn(str)':
bank.cpp:168:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |  void setIn(str S)  { freopen(S.c_str(),"r",stdin); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bank.cpp: In function 'void FileIO::setOut(str)':
bank.cpp:169:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |  void setOut(str S) { freopen(S.c_str(),"w",stdout); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29