Submission #146806

#	Time	Username	Problem	Language	Result	Execution time	Memory
146806		rKrPaN	San (COCI17_san)	C++98	120 / 120	269 ms	8760 KiB

san

#include <iostream>
#include <vector>
#include <algorithm>

typedef long long ll;

using namespace std;

vector <ll> hi;
vector <ll> zl;
vector <ll> siz;
vector <pair <ll, ll> > v1;
vector <ll> v2[45];

int main (){
	
	ll cnter = 0;
	ll n,k;
	cin >> n >> k;
	
	for (int i = 0; i < n; i++){
		ll a,b;
		cin >> a >> b;
		hi.push_back(a);
		zl.push_back(b);
		siz.push_back(a);
	}

	sort(siz.begin(), siz.end());
	siz.erase(unique(siz.begin(), siz.end()), siz.end());
	
	for (int i = 0; i < hi.size(); i++){
		hi[i] = lower_bound(siz.begin(), siz.end(), hi[i]) - siz.begin();
	}
	for (int mask = 0; mask < (1 << (n/2)); mask++){
		ll h = 0;
		ll cnt = 0;
		for (int i = 0; i < n/2; i++){
			if ((mask & (1<<i)) > 0){
				if (hi[i] >= h)h = hi[i];
				else {h = -1; break;}
				cnt+= zl[i];
			}
		}
		if (h != -1){
			v1.push_back(make_pair(h, cnt));
			if (cnt >= k)cnter++;
		}
	}
	
	int xyz = n/2;
	if (n%2 == 1)xyz++;
	for (int mask = 0; mask < (1 << xyz); mask++){
		ll mask2 = ((ll)mask << (n/2));
		ll mh = -1;
		ll h = 0;
		ll cnt = 0;
		for (int i = n/2; i < n; i++){
			if ((mask2 & (1ll<<i)) > 0){
				if (mh == -1)mh = hi[i];
				if (hi[i] >= h)h = hi[i];
				else {h = -1; break;}
				cnt+= zl[i];
			}
		}
		if (h != -1){
			v2[mh].push_back(cnt);
		}
	}
	
	for (int i = 0; i < 45; i++)
		sort(v2[i].begin(), v2[i].end());
		
	for (int i = 0; i < v1.size(); i++){
		ll h = v1[i].first;
		ll z = v1[i].second;
		for (int j = h; j < 42; j++){
			int l = lower_bound(v2[j].begin(), v2[j].end(), k-z) - v2[j].begin();
			cnter += v2[j].size() - l;
		}
		
	}
	cout << cnter << "\n";

	
	return 0;
}

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < hi.size(); i++){
                  ~~^~~~~~~~~~~
san.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v1.size(); i++){
                  ~~^~~~~~~~~~~

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