oj.uz

Submission #146723

# Submission time Handle Problem Language Result Execution time Memory
146723 2019-08-25T16:00:52 Z BartolM San (COCI17_san) C++17
24 / 120
 202 ms 10704 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++;
		//	cout << h << " " << cnt << "\n";
		}
	}
//cout << ".\n";
	for (int mask = 0; mask < (1 << (n/2)); mask++){
		int mask2 = (mask << n/2);
		ll h = 0;
		ll 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++){
		ll h = v1[i].first;
		ll 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:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < hi.size(); i++){
                  ~~^~~~~~~~~~~
san.cpp:74: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 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't 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 376 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 24.0

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

Subtask #5
0 / 24.0

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