結果
問題 | No.1701 half price |
ユーザー |
![]() |
提出日時 | 2021-11-08 16:49:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 289 ms / 3,000 ms |
コード長 | 4,989 bytes |
コンパイル時間 | 4,684 ms |
コンパイル使用メモリ | 244,720 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 11:53:28 |
合計ジャッジ時間 | 5,981 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;using ll=long long;using ld=long double;using vvi=vector<vector<int>>;using vi=vector<int>;using vpi=vector<pair<int,int>>;using vvl=vector<vector<ll>>;using vl=vector<ll>;using vpl=vector<pair<ll,ll>>;using vb=vector<bool>;using vvb=vector<vb>;using mint=modint1000000007;using mint9=modint998244353;using P=pair<ll,ll>;using Pi=pair<int,int>;#define outs cout << " ";#define outl cout << endl;ll mod1=1000000007,mod2=998244353;ll intmax=2147483647,llmax=9223372036854775807;#define rep(i, s, n) for (ll i = s; i < (ll)(n); i++)#define dep(i, s, n) for (ll i = n-1; i >=(ll)(s); i--)#define rem(i, s, n, t) for(ll i = s; i < (ll)(n); t, i++)#define dem(i, s, n, t) for(ll i = n-1; i >=(ll)(s); t, i--)#define all(a) (a).begin(),(a).end()#define allr(a) (a).rbegin(),(a).rend()#define nr cout << "No" << endl;return 0;#define print(a) cout << a << " ";#define np next_permutation#define fi first#define se second#define sor(a) sort(all(a))#define sorr(a) sort(allr(a))#define grl greater<ll>#define gri greater<int>#define sizel(a) ll(a.size())#define pb push_back#define alout(a) {rep(i,0,a.size())cout << a[i] << " ";outl;}#define chmax(a,b) a=max(a,b);#define chmin(a,b) a=min(a,b);void fix(ll a){cout << fixed << setprecision(a);}void yn(bool a){if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}void alllut(vi s){rep(i,0,s.size())cout << s[i] << " ";outl;}void allout(vl s){rep(i,0,s.size()-1)cout << s[i] << " ";cout << s[s.size()-1] << endl;}void ifout(bool a,ll x,ll y){cout << ((a)?x:y);}void paut(pair<ll,ll> s){cout << s.fi << " " << s.se << endl;}void pout(pair<ll,ll> s){cout << s.fi << " " << s.se << endl;}ll keta(ll i,ll j){i=i%ll(pow(10,j))/ll(pow(10,j-1));return i;}// j = 0 は ダメll pm1(ll x,ll y){ll s=1;for(ll i=0;i<y;i++)s=s*x%mod1;return s;}ll pm2(ll x,ll y){ll s=1;for(ll i=0;i<y;i++)s=s*x%mod2;return s;}mint cnvm(ll x,ll y){if(x<y)return 0;mint s=1;rep(i,1,y+1){s=s*(x+1-i)/i;}return s;}mint9 cnvm9(ll x,ll y){if(x<y)return 0;mint9 s=1;rep(i,1,y+1){s=s*(x+1-i)/i;}return s;}ll cnv(ll x,ll y){if(x<y)return 0;ll s=1;rep(i,1,y+1){s=s*(x+1-i)/i;}return s;}ll gcd(ll a,ll b){for(;min(a,b)>0;)if(a<b)b%=a;else a%=b;return max(a,b);}ll lcm(ll a,ll b){return a/gcd(a,b)*b;}string tak="Takahashi",aok="Aoki",yes="Yes",no="No",fir="First",sec="Second";ll kosuu(ll a,ll b){return max(ll(0),b-a+1);}ll modpow(ll a,ll b,ll mod=llmax){ll ans=1;while(b){if(b%2==1)ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;}void asdf(){cout << "?" << endl;}/*ll l=0,r=a.size();while(l+1<r){ll w=(l+r)/2;if(w<(=:tarを含むとき)tar)else}*/// '0'=48, 'A'=65, 'Z'=90, 'a'=97', 'z'=122string tolower(string s){rep(i,0,s.size())if(s[i]<91)s[i]=s[i]+32;return s;}string toupper(string s){rep(i,0,s.size())if(s[i]>96)s[i]=s[i]-32;return s;}ll MAX,mod=mod1;vl fac,finv,inv;void COMinit(){MAX++;fac.resize(MAX);finv.resize(MAX);inv.resize(MAX);fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;rep(i,2,MAX){fac[i]=fac[i-1]*i%mod;inv[i]=mod-inv[mod%i]*(mod/i)%mod;finv[i]=finv[i-1]*inv[i]%mod;}}ll com(ll n,ll k){if(n<k)return 0;if(n<0||k<0)return 0;return fac[n]*(finv[k]*finv[n-k]%mod)%mod;}ll MAx;vl fact;void FACT(){fact=vl(MAx+1,1);rep(i,1,MAx+1)fact[i]=fact[i-1]*i;}ll upper(vl a,ll b){//if(a[0]>b)ll l=0,r=a.size()-1;while(l+1<r){ll w=(l+r)/2;if(a[w]<=b)l=w;else r=w;}return l+1;}ll lower(vl a,ll b){ll l=0,r=a.size()-1;while(l+1<r){ll w=(l+r)/2;if(a[w]<b)l=w;else r=w;}return l+1;}ll dai(ll n){vi s;while(n){s.push_back(n%10);n/=10;}sort(all(s));for(int i=s.size()-1;i>-1;i--){n+=s[i]*pow(10,i);}return n;}ll syou(ll n){vi s;while(n){s.push_back(n%10);n/=10;}sort(all(s));rep(i,0,s.size()){n+=s[i]*pow(10,s.size()-i-1);}return n;}ll yakusuu(ll a){ll co=0;for(ll i=1;i*i<a;i++)if(a%i==0)co+=2;if(a==pow((int)sqrt(a),2))co++;return co;}void pin(P &a){cin>>a.fi>>a.se;}bool prime(ll a){rep(i,2,sqrt(a)+1)if(a%i==0)return 0;return 1;}ll LIS(vl a){vl ret;for(ll u:a){auto itr=lower_bound(all(ret),u);if(itr!=ret.end())*itr=u;else ret.push_back(u);}return ll(ret.size());}// priority_queue<ll,vl,grl> greaterll sl=1,ls=0,inf=1e18;// segtree l~r-1P f(P a,P b){return make_pair(max(a.fi,b.fi),(a.fi>=b.fi?a.se:b.se));//return ret;}P s(){return make_pair(ls,ls);//return ret;}int main(){ll n,w;cin>>n>>w;vl a(n);rep(i,0,n)cin>>a[i];set<ll> st;rep(bit,1,modpow(3,n)){vl b(n);ll bi=bit;rep(i,0,n)b[i]=bi%3,bi/=3;ll as=0;rep(i,0,n)as+=a[i]*b[i]/2;if(as!=w)continue;as=0;rep(i,0,n)if(b[i]!=0)as+=modpow(2,i);st.insert(as);}cout << st.size() << endl;}