結果
問題 | No.1701 half price |
ユーザー |
![]() |
提出日時 | 2021-10-08 22:34:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 67 ms / 3,000 ms |
コード長 | 797 bytes |
コンパイル時間 | 1,678 ms |
コンパイル使用メモリ | 176,856 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-23 05:33:44 |
合計ジャッジ時間 | 2,530 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const ll MOD = 1000000007;using P = pair<int,int>;#define rep(i, n) for(int i = 0; i < n; i++)#define all(x) (x).begin(),(x).end()int main(){ll n,w;cin >> n >> w;vector<ll> a(n);rep(i,n) cin >> a[i];ll ans = 0;rep(i,pow(2,n)){if(!i) continue;ll tot = 0;set<ll> dec, dec2;dec.insert(0); dec2.insert(0);int x = i, j = 0;while(x){if(x%2){tot += a[j];for(ll y:dec){dec2.insert(y+a[j]/2);}dec = dec2;}j++;x /= 2;}ans += dec.count(tot - w);}cout << ans << endl;return 0;}