oj.uz

Submission #37045

# Submission time Handle Problem Language Result Execution time Memory
37045 2017-12-20T16:23:13 Z Dat160601 San (COCI17_san) C++14
120 / 120
 176 ms 9348 KB 
#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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2996 KB Output is correct
2 Correct 0 ms 2160 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4172 KB Output is correct
2 Correct 3 ms 2436 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 9348 KB Output is correct
2 Correct 19 ms 4180 KB Output is correct