Submission #37045

#	Time	Username	Problem	Language	Result	Execution time	Memory
37045		Dat160601	San (COCI17_san)	C++14	120 / 120	176 ms	9348 KiB

san

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n,hi[43];
long long m,gold[43],ans=0;
vector <long long> val,val_left[43],val_right[43];
void backtrack_left(int cur,int last,long long sum){
	if(cur==(n+3)/2){
		int pos=lower_bound(val.begin(),val.end(),last)-val.begin();
		val_left[pos].pb(sum);
		return;
	}
	backtrack_left(cur+1,last,sum);
	if(hi[cur]>=last){
		backtrack_left(cur+1,hi[cur],sum+gold[cur]);
	}
}
void backtrack_right(int cur,int last,int fr,long long sum){
	if(cur==n+1){
		int pos=lower_bound(val.begin(),val.end(),fr)-val.begin();
		val_right[pos].pb(sum);
		return;
	}
	backtrack_right(cur+1,last,fr,sum);
	if(hi[cur]>=last){
		if(fr==0) fr=hi[cur];
		backtrack_right(cur+1,hi[cur],fr,sum+gold[cur]);
	}
}
int main(){
	cin>>n>>m;
	val.pb(0);
	for(int i=1;i<=n;i++){
		cin>>hi[i]>>gold[i];
		val.pb(hi[i]);
	}
	sort(val.begin(),val.end());
	backtrack_left(1,0,0);
	backtrack_right((n+3)/2,0,0,0);
	n=(int)val.size();
	for(int i=0;i<n;i++) sort(val_right[i].begin(),val_right[i].end());
	for(int i=0;i<n;i++){
		for(int j=0;j<(int)val_left[i].size();j++){
			long long curval=val_left[i][j];
			ans+=val_right[0].end()-lower_bound(val_right[0].begin(),val_right[0].end(),m-curval);
			for(int ij=i;ij<n;ij++){
				if(ij==0) continue;
				ans+=val_right[ij].end()-lower_bound(val_right[ij].begin(),val_right[ij].end(),m-curval);
			}
		}
	}
	cout<<ans;
}

• Subtask 1: 24 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24