oj.uz

Submission #44364

# Submission time Handle Problem Language Result Execution time Memory
44364 2018-03-31T19:15:00 Z JustInCase San (COCI17_san) C++17
120 / 120
 220 ms 21308 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;
vector< int64_t > grouped[MAX_N];

void Compress() {
	vector< int32_t > v(n + 1);
	for(int32_t i = 1; i <= n; i++) {
		v[i] = height[i];
	}

	sort(v.begin() + 1, v.end());
	v.erase(unique(v.begin() + 1, v.end()), v.end());

	for(int32_t i = 1; i <= n; i++) {
		height[i] = lower_bound(v.begin() + 1, v.end(), height[i]) - v.begin();
	}
}

void BruteForceLeft(int32_t ind, int64_t cntCoins) {
	leftSide.push_back({ height[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({ height[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];
	}

	Compress();
	
	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]);
	}
	
	int64_t ans = 0;	
	for(auto x : leftSide) {
		if(x.second >= k) {
			ans++;
		}
	}
	for(auto x : rightSide) {
		if(x.second >= k) {
			ans++;
		}
	}

	for(auto x : rightSide) {
		grouped[x.first].push_back(x.second);
	}
	for(int32_t i = 1; i <= n; i++) {
		sort(grouped[i].begin(), grouped[i].end());
	}

	for(auto x : leftSide) {
		for(int32_t i = x.first; i <= n; i++) {
			int32_t low = 0, high = grouped[i].size() - 1, ansInd = -1;
			
			if(grouped[i].size() == 0) {
				continue;
			}
			
			while(low <= high) {
				int32_t mid = (low + high) / 2;

				if(grouped[i][mid] + x.second >= k) {
					high = mid - 1;
					ansInd = mid;
				}
				else {
					low = mid + 1;
				}
			}

			if(ansInd == -1) {
				continue;
			}
			
			ans += 1ll * grouped[i].size() - ansInd;
		}
	}

	cout << ans << endl;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2804 KB Output is correct
2 Correct 3 ms 2804 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5564 KB Output is correct
2 Correct 8 ms 5564 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 21308 KB Output is correct
2 Correct 30 ms 21308 KB Output is correct