#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
int n;
long long h[45], g[45], lol;
long long amount = 0;
vector<long long> graph[2][45], data;
void backtrack(int pos, int limit, long long height, long long sum, long long dist){
if(pos == limit + 1){
if(sum == 0) return ;
//cout << sum << "\n";
if(limit == n / 2){
int it = lower_bound(data.begin(), data.end(), height) - data.begin();
graph[0][it].pb(sum);
}
else{
int it = lower_bound(data.begin(), data.end(), dist) - data.begin();
graph[1][it].pb(sum);
}
return ;
}
backtrack(pos + 1, limit, height, sum, dist);
if(h[pos] >= height){
if(dist == -1 && limit == n)
backtrack(pos + 1, limit, h[pos], sum + g[pos], h[pos]);
else if(limit == n)
backtrack(pos + 1, limit, h[pos], sum + g[pos], dist);
else if(limit == n / 2)
backtrack(pos + 1, limit, h[pos], sum + g[pos], dist);
}
}
int main() {
cin.tie(0), ios::sync_with_stdio(0);
cin >> n >> lol;
for(int i = 1; i <= n; i++){
cin >> h[i] >> g[i];
data.pb(h[i]);
}
sort(data.begin(), data.end());
data.erase(unique(data.begin(),data.end()),data.end());
backtrack(1, n / 2, -1, 0, -1);
backtrack(n / 2 + 1, n, -1, 0, -1);
for(int i = 0; i < data.size(); i++){
for(int j = 0; j < 2; j++){
for(int l = 0; l < graph[j][i].size(); l++){
if(graph[j][i][l] >= lol)
amount++;
}
sort(graph[j][i].begin(), graph[j][i].end());
}
}
//cout << amount << "\n";
for(int i = 0; i < data.size(); i++){
for(int j = 0; j < graph[0][i].size(); j++){
for(int k = i; k < data.size(); k++){
//cout << data[i] << " " << data[k] << " " << graph[0][i].size() << " " << graph[1][k].size() << "\n";
if(graph[1][k].size() == 0) continue;
//if(graph[0][i][j] >= k) {amount += graph[1][k].size(); continue;}
int l = 0, r = graph[1][k].size() - 1, mid;
while(l < r){
mid = (l + r) / 2;
if(graph[0][i][j] + graph[1][k][mid] >= lol)
r = mid;
else
l = mid + 1;
}
if(graph[0][i][j] + graph[1][k][l] >= lol)
amount += graph[1][k].size() - l;
}
}
}
cout << amount << "\n";
}
/*4 15
5 5
5 12
6 10
2 1*/
Compilation message
san.cpp: In function 'int main()':
san.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < data.size(); i++){
~~^~~~~~~~~~~~~
san.cpp:55:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int l = 0; l < graph[j][i].size(); l++){
~~^~~~~~~~~~~~~~~~~~~~
san.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < data.size(); i++){
~~^~~~~~~~~~~~~
san.cpp:64:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < graph[0][i].size(); j++){
~~^~~~~~~~~~~~~~~~~~~~
san.cpp:65:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = i; k < data.size(); k++){
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
468 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
1520 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
2276 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
7968 KB |
Output is correct |
| 2 |
Correct |
33 ms |
7968 KB |
Output is correct |
