Submission #116862

#	Time	Username	Problem	Language	Result	Execution time	Memory
116862		HungAnhGoldIBO2020	San (COCI17_san)	C++11	120 / 120	200 ms	6652 KiB

san

#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int N=42;
const int inf=1e18;
pair<int,int> ar[N];
vector<int> val[N],val1[N];
signed main(){
	int n,i,j,k,l,num,pos;
	int ans=0;
	cin>>n>>num;
	for(i=1;i<=n;i++){
		cin>>ar[i].first>>ar[i].second;
	}
	if(n==1){
		if(ar[1].second>=num){
			cout<<1;
		}
		else{
			cout<<0;
		}
	}
	for(i=1;i<(1ll<<(n/2));i++){
		k=0,l=0;
		for(j=1;j<=n/2;j++){
			if(((1<<(j-1))&i)){
				if(ar[j].first<l){
					break;
				}
				k+=ar[j].second;
				l=ar[j].first;
				pos=j;
			}
			if(j==n/2){
				val[pos].push_back(k);
				//cout<<pos<<" "<<k<<endl;	
				if(k>=num){
					ans++;
				}
			}
		}
	}
	for(i=1;i<(1ll<<(n-n/2));i++){
		k=0,l=inf;
		for(j=n;j>n/2;j--){
			if(((1<<(j-n/2-1))&i)){
				if(ar[j].first>l){
					break;
				}
				k+=ar[j].second;
				l=ar[j].first;
				pos=j;
			}
			if(j==n/2+1){
				val1[pos].push_back(k);
				//cout<<pos<<" "<<k<<endl;
				if(k>=num){
					ans++;
				}
			}
		}
	}
	for(i=1;i<=n/2;i++){
		sort(val[i].begin(),val[i].end());
	}
	for(i=n/2+1;i<=n;i++){
		sort(val1[i].begin(),val1[i].end());
	}
	for(i=1;i<=n/2;i++){
		for(j=n/2+1;j<=n;j++){
			if(ar[i].first<=ar[j].first){
				for(k=0;k<val[i].size();k++){
					l=lower_bound(val1[j].begin(),val1[j].end(),num-val[i][k])-val1[j].begin();
					ans+=val1[j].size()-l;
				}
			}
		}
	}
	cout<<ans;
}

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:74:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(k=0;k<val[i].size();k++){
             ~^~~~~~~~~~~~~~

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