oj.uz

Submission #146806

# Submission time Handle Problem Language Result Execution time Memory
146806 2019-08-26T08:41:23 Z rKrPaN San (COCI17_san) C++
120 / 120
 269 ms 8760 KB 
#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

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

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 22 ms 1388 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2156 KB Output is correct
2 Correct 23 ms 1012 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 8760 KB Output is correct
2 Correct 122 ms 2536 KB Output is correct