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>
using namespace std;
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
ll n,k,ans=0;
pair<ll,ll> a[50];
vector < ll > data_left[43],data_right[43],data;
void bt_left(int start,ll val,int high){
if(start==(n+3)/2){
int pos=lower_bound(data.begin(),data.end(),high)-data.begin();
data_left[pos].pb(val);
return ;
}
bt_left(start+1,val,high);
if(a[start].fi>=high){
bt_left(start+1,val+a[start].se,a[start].fi);
}
}
void bt_right(int i,int high,int fr,ll val){
if(i==n+1){
int pos=lower_bound(data.begin(),data.end(),fr)-data.begin();
data_right[pos].pb(val);
return;
}
bt_right(i+1,high,fr,val);
if(a[i].fi>=high){
if(fr==0)
fr=a[i].fi;
bt_right(i+1,a[i].fi,fr,val+a[i].se);
}
}
int main()
{
cin>>n>>k;
data.pb(0);
for(int i=1;i<=n;i++)
{
cin>>a[i].fi>>a[i].se;
data.pb(a[i].fi);
}
sort(data.begin(),data.end());
//for(int i=0;i<data.size();i++)
// cout<<data[i]<<' ';
//cout<<endl<<endl;
bt_left(1,0,0);
bt_right((n+3)/2,0,0,0);
n=data.size();
for(int i=0;i<n;i++) {
sort(data_right[i].begin(),data_right[i].end());
//for(int j=0;j<data_right[i].size();j++)
// cout<<data_right[i][j]<<' ';
//cout<<endl;
}
for(int i=0;i<n;i++){
for(int j=0;j<data_left[i].size();j++){
ll x=data_left[i][j];
//ans+=data_right[0].end()-lower_bound(data_right[0].begin(),data_right[0].end(),k-x);
for(int ij=i;ij<n;ij++){
//if(ij==0) continue;
ans+=data_right[ij].end()-lower_bound(data_right[ij].begin(),data_right[ij].end(),k-x);
}
}
}
cout<<ans;
}
Compilation message (stderr)
san.cpp: In function 'int main()':
san.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<data_left[i].size();j++){
^
# | 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... |