Submission #44363

#	Time	Username	Problem	Language	Result	Execution time	Memory
44363		JustInCase	San (COCI17_san)	C++17	48 / 120	1087 ms	21316 KiB

san

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int32_t MAX_N = 45;

int32_t n, height[MAX_N], coins[MAX_N];
vector< pair< int32_t, int64_t > > leftSide, rightSide;

void BruteForceLeft(int32_t ind, int64_t cntCoins) {
	leftSide.push_back({ ind, cntCoins });

	for(int32_t i = ind + 1; i <= n / 2; i++) {
		if(height[i] >= height[ind]) {
			BruteForceLeft(i, cntCoins + 1ll * coins[i]);
		}
	}
}

void BruteForceRight(int32_t ind, int64_t cntCoins) {
	rightSide.push_back({ ind, cntCoins });

	for(int32_t i = ind - 1; i > n / 2; i--) {
		if(height[i] <= height[ind]) {
			BruteForceRight(i, cntCoins + 1ll * coins[i]);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int64_t k;
	cin >> n >> k;

	for(int32_t i = 1; i <= n; i++) {
		cin >> height[i] >> coins[i];
	}
	
	if(n == 1) {
		if(coins[1] >= k) {
			cout << 1 << endl;
		}
		else {
			cout << 0 << endl;
		}

		return 0;
	}
	
	for(int32_t i = 1; i <= n / 2; i++) {
		BruteForceLeft(i, coins[i]);
	}

	for(int32_t i = n; i > n / 2; i--) {
		BruteForceRight(i, coins[i]);
	}
	
	int32_t ans = 0;
	
	for(auto x : leftSide) {
		if(x.second >= k) {
			ans++;
		}
	}
	for(auto x : rightSide) {
		if(x.second >= k) {
			ans++;
		}
	}

	for(auto x : leftSide) {
		for(auto y : rightSide) {
			if(height[x.first] <= height[y.first]) {
				if(1ll * x.second + 1ll * y.second >= k) {
					ans++;
				}
			}
		}
	}

	cout << ans << endl;
}

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