This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef double D;
const ll inf=(1ll<<61);
const int mod=1e9+7;
const int MX=20;
const int SQ=350;
int n,m;
ll k;
pair<ll,ll>a[MX];
vector<ll>v1[30];
vector<pair<ll,ll> >v;
void calc1(int x,ll sum,int fin,int height){
if(x==fin){
if(height)
v.push_back({height,sum});
return;
}
calc1(x+1,sum,fin,height);
if(a[x].first>=height)calc1(x+1,sum+a[x].second,fin,a[x].first);
}
void calc2(int x,ll sum,int fin,int height,int ind){
if(x==fin){
v1[ind].push_back(sum);
return;
}
calc2(x+1,sum,fin,height,ind);
if(a[x].first>=height)calc2(x+1,sum+a[x].second,fin,a[x].first,ind);
}
int main(){
scanf("%d%lld",&n,&k);
for(int i=0;i<n;i++){
scanf("%lld%lld",&a[i].first,&a[i].second);
}
calc1(0,0,n/2,0);
for(int i=n/2;i<n;i++){
calc2(i+1,a[i].second,n,a[i].first,i);
}
ll ans=0;
for(int i=n/2;i<n;i++){
sort(v1[i].begin(),v1[i].end());
for(auto pp:v1[i]){
if(pp>=k)ans++;
}
}
for(auto pp:v){
ll h=pp.first,money=pp.second;
if(money>=k)ans++;
for(int i=n/2;i<n;i++){
if(a[i].first>=h){
if(lower_bound(v1[i].begin(),v1[i].end(),k-money)==v1[i].end())continue;
ans+=lower_bound(v1[i].begin(),v1[i].end(),k-money)-v1[i].begin()+1;
}
}
}
cout<<ans<<endl;
}
Compilation message (stderr)
san.cpp: In function 'int main()':
san.cpp:33:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%lld",&n,&k);
^
san.cpp:35:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&a[i].first,&a[i].second);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |