oj.uz

Submission #44363

# Submission time Handle Problem Language Result Execution time Memory
44363 2018-03-31T18:48:45 Z JustInCase San (COCI17_san) C++17
48 / 120
 1000 ms 21316 KB 
#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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 472 KB Output is correct
2 Correct 2 ms 476 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 2156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 5476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 21316 KB Time limit exceeded
2 Halted 0 ms 0 KB -