Submission #759212

#TimeUsernameProblemLanguageResultExecution timeMemory
759212sofija6Ice Hockey World Championship (CEOI15_bobek)C++14
60 / 100
1082 ms166768 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 50 using namespace std; ll a[MAXN],m; set<ll> s1,s2; map<ll,ll> cnt1,cnt2; void Solve(ll l,ll r,ll cur,ll pos,set<ll> &s,map<ll,ll> &cnt) { if (pos>r) { if (cur>m) return; s.insert(cur); cnt[cur]++; return; } Solve(l,r,cur,pos+1,s,cnt); Solve(l,r,cur+a[pos],pos+1,s,cnt); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n,ans=0; cin >> n >> m; for (ll i=1;i<=n;i++) cin >> a[i]; Solve(1,n/2,0,1,s1,cnt1); Solve(n/2+1,n,0,n/2+1,s2,cnt2); ll cur=0; for (auto i : s2) { cur+=cnt2[i]; cnt2[i]=cur; } for (auto i : s1) { auto it=s2.lower_bound(m-i); if ((*it)!=m-i) { if (it==s2.begin()) continue; it--; } ans+=cnt1[i]*cnt2[*it]; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...