oj.uz

Submission #116862

# Submission time Handle Problem Language Result Execution time Memory
116862 2019-06-14T02:57:11 Z HungAnhGoldIBO2020 San (COCI17_san) C++11
120 / 120
 200 ms 6652 KB 
#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

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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1216 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1816 KB Output is correct
2 Correct 32 ms 512 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 6652 KB Output is correct
2 Correct 114 ms 1648 KB Output is correct