oj.uz

Submission #82576

# Submission time Handle Problem Language Result Execution time Memory
82576 2018-10-31T14:11:26 Z thiago4532 San (COCI17_san) C++17
0 / 120
 139 ms 596 KB 
#include <bits/stdc++.h>
#define int int64_t
#define ff first
#define ss second

using namespace std;
typedef pair<int, int> pii;
const int maxn = 80;
int hl[maxn], cl[maxn], hr[maxn], cr[maxn];
int n, k;
vector<int> hg[maxn];
vector<pii> pp;

int32_t main(){
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> k;

	int nl = (n/2);
	int nr = n - (n/2);

	for(int i=1;i<=nl;i++)
		cin >> hl[i] >> cl[i];

	for(int i=1;i<=nr;i++)
		cin >> hr[i] >> cr[i], pp.push_back({hr[i], i});
	sort(pp.begin(), pp.end());

	vector<pii> l, r;
	int ans=0;

	for(int i=1;i<(1<<nl);i++){

		int hlast=-1;

		bool possible = true;

		int num=0;
		for(int j=1;j<=nl;j++){
			if(i&(1<<(j-1))){
				num += cl[j];
				if(hl[j] < hlast) possible = false;
				hlast = hl[j];
			}
		}
		//possible &= (num >= k);

		if(possible && (num >= k)) ans++;
		else if(possible) l.push_back({hlast, num});
	}

	for(int i=1;i<(1<<nr);i++){

		int hlast=-1, hf=-1;

		bool possible = true;

		int num=0;
		for(int j=1;j<=nr;j++){
			if(i&(1<<(j-1))){
				if(hf == -1) hf = hr[j];

				num += cr[j];
				if(hr[j] < hlast) possible = false;
				hlast = hr[j];
			}
		}
		//possible &= (num >= k);

		if(possible && (num >= k)) ans++;
		else if(possible) r.push_back({hf, num});
	}
	sort(r.begin(), r.end());

	for(auto &p : r)
		for(int i=1;i<=nr;i++)
			if(p.ff >= hr[i]) hg[i].push_back(p.ss);

	for(int i=1;i<=nr;i++)
		sort(hg[i].begin(), hg[i].end());

	for(auto& p : l){
		auto it = lower_bound(pp.begin(), pp.end(), pii{p.ff, -1});
		if(it == pp.end()) continue;
		int pos = it->ss;

		int px = hg[pos].size() - (lower_bound(hg[pos].begin(), hg[pos].end(), k-p.ss) - hg[pos].begin());
		ans += px;

		//cout << p.ff << " " << p.ss << " " << px << "\n";
	}
	cout << (ans?ans+1:0) << "\n";
	return 0;
}

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 Incorrect 2 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 24.0

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

Subtask #5
0 / 24.0

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