Submission #113122

#TimeUsernameProblemLanguageResultExecution timeMemory
113122ioilolcomIce Hockey World Championship (CEOI15_bobek)C++14
100 / 100
378 ms21004 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define all(s) s.begin(),s.end() typedef long long int ll; vector<ll> v1,v2,v; vector<ll>d1,d2; ll n,m; void solve(int idx,ll s,int t){ if(t==1) { if(idx==(int)v1.size()) { if(s<=m) d1.push_back(s); return; } solve(idx+1,s+v1[idx],t); solve(idx+1,s,t); } else{ if(idx==(int)v2.size()) { if(s<=m) d2.push_back(s); return; } solve(idx+1,s+v2[idx],t); solve(idx+1,s,t); } } ll l=0; void solv(int idx,ll s){ if(idx==n) { if(s<=m) { l++; } return; } solv(idx+1,s+v[idx]); solv(idx+1,s); } int main() { ios_base:: sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=1; i<=n; i++) { ll a; cin>>a; v.push_back(a); if(i&1) v1.push_back(a); else v2.push_back(a); } solve(0,0,1); solve(0,0,2); ll ans=0; //solv(0,0); /* cout<<"one"<<endl; for(int v:v1) { cout<<v<<" "; } cout<<endl; cout<<"two"<<endl; for(int v:v2) { cout<<v<<" "; } cout<<endl; */ sort(all(d2)); //cout<<"set 1"<<endl; for(ll v:d1) { // cout<<v<<endl; int l=0; int r=(int)d2.size()-1; int an=-1; while(l<=r) { int mid=(l+r)/2; if(d2[mid]+v<=m) { an=mid; l=mid+1; } else{ r=mid-1; } } //cout<<"max "<<an<<endl; if(an!=-1) ans+=(an+1); } cout<<ans<<endl; // solv(0,0); //cout<<l<<endl; /* cout<<"set 2"<<endl; for(int v:d2) { cout<<v<<endl; // auto it=lower_bound(all(d2),m-v); //cout<<(distance(d2.begin(),it))<<endl; } */ //cout<<ans<<endl; 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...