#include <bits/stdc++.h>
#define int int64_t
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 80;
int hl[maxn], cl[maxn], hr[maxn], cr[maxn];
int n, k;
vector<int> hg[maxn];
vector<pii> pp;
int32_t main(){
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> k;
int nl = (n/2);
int nr = n - (n/2);
for(int i=1;i<=nl;i++)
cin >> hl[i] >> cl[i];
for(int i=1;i<=nr;i++)
cin >> hr[i] >> cr[i], pp.push_back({hr[i], i});
sort(pp.begin(), pp.end());
vector<pii> l, r;
int ans=0;
for(int i=1;i<(1<<nl);i++){
int hlast=-1;
bool possible = true;
int num=0;
for(int j=1;j<=nl;j++){
if(i&(1<<(j-1))){
num += cl[j];
if(hl[j] < hlast) possible = false;
hlast = hl[j];
}
}
//possible &= (num >= k);
if(possible && (num >= k)) ans++;
if(possible) l.push_back({hlast, num});
}
for(int i=1;i<(1<<nr);i++){
int hlast=-1, hf=-1;
bool possible = true;
int num=0;
for(int j=1;j<=nr;j++){
if(i&(1<<(j-1))){
if(hf == -1) hf = hr[j];
num += cr[j];
if(hr[j] < hlast) possible = false;
hlast = hr[j];
}
}
//possible &= (num >= k);
if(possible && (num >= k)) ans++;
if(possible) r.push_back({hf, num});
}
sort(r.begin(), r.end());
for(auto &p : r){
//cout << "COMBINACOES: " << p.ff << " " << p.ss << "\n";
for(int i=1;i<=nr;i++)
if(p.ff >= hr[i]) hg[i].push_back(p.ss);
}
for(int i=1;i<=nr;i++)
sort(hg[i].begin(), hg[i].end());
for(auto& p : l){
auto it = lower_bound(pp.begin(), pp.end(), pii{p.ff, -1});
if(it == pp.end()) continue;
int pos = it->ss;
int px = hg[pos].size() - (lower_bound(hg[pos].begin(), hg[pos].end(), k-p.ss) - hg[pos].begin());
ans += px;
//cout << p.ff << " " << p.ss << " " << hr[pos] << "\n";
}
cout << ans << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
508 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
3016 KB |
Output is correct |
2 |
Correct |
15 ms |
3016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
95 ms |
7592 KB |
Output is correct |
2 |
Correct |
77 ms |
7592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
363 ms |
30016 KB |
Output is correct |
2 |
Correct |
212 ms |
30016 KB |
Output is correct |