結果
問題 | No.1701 half price |
ユーザー |
|
提出日時 | 2021-10-21 18:57:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 3,000 ms |
コード長 | 2,273 bytes |
コンパイル時間 | 4,812 ms |
コンパイル使用メモリ | 255,660 KB |
最終ジャッジ日時 | 2025-01-25 02:29:29 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#pragma region Macros#include <bits/stdc++.h>#if defined(LOCAL) || defined(ONLINE_JUDGE) || defined(_DEBUG)#include <atcoder/all>#endifusing namespace std;#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)#define REPR(i, n) for(int i=(n); i>=0; --i)#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)#define EACH(i, v) for(const auto& i : v)#define ALL(x) (x).begin(),(x).end()#define ALLR(x) (x).rbegin(),(x).rend()template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }template<class T>using vec = vector<T>;template<class T, class U>using umap = unordered_map<T, U>;template<class T>using uset = unordered_set<T>;using ll = long long;using ld = long double;using P = pair<ll, ll>;using T = tuple<ll, ll, ll>;using vl = vec<ll>;#define fi first#define se second#define el endlconstexpr ll INF = numeric_limits<ll>::max()/2-1;#pragma endregion#pragma region IOMacrostemplate<class T>istream &operator>>(istream &stream, vec<T>& o){REP(i, o.size())stream >> o[i];return stream;}template<class T>ostream &operator<<(ostream &stream, vec<T>& objs){REP(i, objs.size())stream << objs[i] << " ";stream << el;return stream;}#define I(T, ...) ;T __VA_ARGS__;__i(__VA_ARGS__);void __i() {}template<class T, class... Ts> void __i(T&& o, Ts&&... args){cin >> o;__i(forward<Ts>(args)...);}void O() {cout << el;}template<class T, class... Ts> void O(T&& o, Ts&&... args){cerr << o << " ";O(forward<Ts>(args)...);}#pragma endregionvoid Main();int main(){std::cin.tie(nullptr);std::cout << std::fixed << std::setprecision(15);Main();return 0;}uset<ll> seen;ll solve(ll yen, const vl &A, ll i, ll bit){--i;if(i < 0){//O(bitset<3>(bit), yen);if(yen == 0 && !seen.count(bit)){seen.insert(bit);return 1;}return 0;}if(yen < 0){return 0;}return solve(yen-A[i], A, i, (bit<<1)|1ll)+solve(yen-A[i]/2, A, i, (bit<<1)|1ll)+solve(yen, A, i, bit<<1);}void Main(){I(ll, N, W);vl A(N);seen.insert(0);cin >> A;cout << solve(W, A, N, 0) << el;}