oj.uz

Submission #146721

# Submission time Handle Problem Language Result Execution time Memory
146721 2019-08-25T15:56:33 Z BartolM San (COCI17_san) C++17
0 / 120
 344 ms 5508 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 1872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 344 ms 5508 KB Output isn't correct
2 Halted 0 ms 0 KB -