Submission #146721

#	Time	Username	Problem	Language	Result	Execution time	Memory
146721		BartolM	San (COCI17_san)	C++17	0 / 120	344 ms	5508 KiB

san

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

using namespace std;

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

int main (){
	
	int cnter = 0;
	int n,k;
	cin >> n >> k;
	
	for (int i = 0; i < n; i++){
		int 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++){
		int h = 0;
		int 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++;
		//	cout << h << " " << cnt << "\n";
		}
	}
//cout << ".\n";
	for (int mask = 0; mask < (1 << (n/2)); mask++){
		int mask2 = (mask << n/2);
		int h = 0;
		int cnt = 0;
		for (int i = n/2; i < n; i++){
			if ((mask2 & (1<<i)) > 0){
				if (hi[i] >= h)h = hi[i];
				else {h = -1; break;}
				cnt+= zl[i];
			}
		}
		if (h != -1){
			v2[h].push_back(cnt);
			//cout << h << " " << cnt << "\n";
		}
	}
	
	for (int i = 0; i < 45; i++)
		sort(v2[i].begin(), v2[i].end());
		
	for (int i = 0; i < v1.size(); i++){
		int h = v1[i].first;
		int z = v1[i].second;
		for (int j = h; j < 45; 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:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < hi.size(); i++){
                  ~~^~~~~~~~~~~
san.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v1.size(); i++){
                  ~~^~~~~~~~~~~

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