oj.uz

Submission #42312

# Submission time Handle Problem Language Result Execution time Memory
42312 2018-02-25T22:47:20 Z wzy San (COCI17_san) C++11
120 / 120
 336 ms 17252 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define eps (int) 1e9
#define pii pair<int,int>
#define int long long

int h[41],g[41], n , k;

vector<int> alt[50];
set<int> t;
map<int,int> compress;
int cnt = 0;

int32_t main(){
	cin>>n>>k;
	vector<pii> v1 , v2;
	int sz1 = n/2 + 1;
	int sz2 = n - sz1;
	for(int i = 0 ; i < sz1 ; i++){
		int x  ,y;
		cin>>x>>y;
		v1.pb(pii(x,y));
		t.insert(x);
	}
	for(int i = 0 ; i< sz2 ; i++){
		int x,y;
		cin>>x>>y;
		v2.pb(pii(x,y));
		t.insert(x);
	}
	for(auto p : t){
		compress[p] = cnt++;
	}
	int ans = 0;
	vector<pii> middle1 , middle2;
	for(int j = 1 ; j < (1<<sz1) ; j++){
		int sumj = 0;
		bool can = true;
		int current = 0;
		for(int i = 0 ; i <sz1; i ++){
			if(1<<i & j){
				if(current <= v1[i].F){
					sumj += v1[i].S;
					current = v1[i].F;
				}
				else can = false;
			}
		}
		if(!can) continue;
		middle1.pb(pii(sumj , current));
		if(sumj >= k) ans++;

	}
	for(int j = 1 ; j  < (1<<sz2);j++){
		int sumj = 0;
		bool can = true;
		int current = 0;
		bool jafoifst = false;
		int ffst = 0;
		for(int i = 0 ; i < sz2 ; i++){
			if(1<<i & j){
				if(current <= v2[i].F){
					sumj += v2[i].S;
					current = v2[i].F;
					if(!jafoifst){
						jafoifst ^= 1;
						ffst = current;
					}
				}
				else can = false;
			}
		}
		if(!can) continue;
		if(sumj >= k) ans++;
		alt[compress[ffst]].pb(sumj);
	}
	for(int i = 0 ; i < 50;i++) sort(alt[i].begin() , alt[i].end());
	for(auto p : middle1){
		int j = compress[p.S];
		for(int w = j ; w < 50 ; w++){
			int l = 0 , r = ((int)alt[w].size()) - 1;
			int ansj  =-1;
			while(l<=r){
				int mid = (l+r)/2;
				if(p.F + alt[w][mid] >= k){
					ansj = mid;
					r = mid - 1;
				}
				else l = mid + 1;
			}
			if(ansj != -1)
			ans += (int ) alt[w].size() - ansj;	
		}
	}
	cout<<ans<<endl;
}

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1972 KB Output is correct
2 Correct 17 ms 1972 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2852 KB Output is correct
2 Correct 82 ms 2852 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 17252 KB Output is correct
2 Correct 271 ms 17252 KB Output is correct