Submission #82582

#	Time	Username	Problem	Language	Result	Execution time	Memory
82582		thiago4532	San (COCI17_san)	C++17	120 / 120	363 ms	30016 KiB

san

#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++;
		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++;
		if(possible) r.push_back({hf, num});
	}
	sort(r.begin(), r.end());

	for(auto &p : r){
		//cout << "COMBINACOES: " << p.ff << " " << p.ss << "\n";
		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 << " " << hr[pos] << "\n";
	}
	cout << ans << "\n";
	return 0;
}

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