#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, int height, long long sum, long long dist){
if(pos == limit + 1){
if(sum == 0) return ;
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++;
}
}
}
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++){
if(graph[1][k].size() == 0) 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){
//cout << graph[0][i][j] << " " << graph[1][k][l] << " " << data[k] << "\n";
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:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < data.size(); i++){
~~^~~~~~~~~~~~~
san.cpp:54:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int l = 0; l < graph[j][i].size(); l++){
~~^~~~~~~~~~~~~~~~~~~~
san.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < data.size(); i++){
~~^~~~~~~~~~~~~
san.cpp:61:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < graph[0][i].size(); j++){
~~^~~~~~~~~~~~~~~~~~~~
san.cpp:62: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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
1488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
2172 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
148 ms |
7868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
