# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
38674 |
2018-01-05T23:20:27 Z |
adamczh1 |
San (COCI17_san) |
C++14 |
|
266 ms |
4804 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
#define SIZE(x) (int)(x).size()
#define ff first
#define ss second
inline ll readi(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N;
ll K, ans;
int H[40], G[40];
vector<ll> v[40];
int main(){
N=readi(), K=readi();
vector<int> h;
for(int i=0; i<N; i++){
H[i]=readi();
h.push_back(H[i]);
G[i]=readi();
}
sort(h.begin(),h.end());
h.erase(unique(h.begin(),h.end()),h.end());
for(int i=0; i<N; i++){
H[i]=lower_bound(h.begin(),h.end(),H[i])-h.begin();
}
int M=N>>1;
for(int mask=1; mask<(1<<M); mask++){
int last=-1;
ll sum=0;
bool ok=1;
for(int i=0; i<M; i++){
if((mask>>i)&1){
if(H[i]<last){
ok=0;
break;
}
last=H[i];
sum+=G[i];
}
}
if(ok){
v[last].push_back(sum);
if(sum>=K) ans++;
}
}
for(int i=0;i<40;i++){
sort(v[i].begin(),v[i].end());
}
for(int mask=1; mask<(1<<(N-M)); mask++){
int lowest=-1;
int last=-1;
ll sum=0;
bool ok=1;
for(int i=0; i<N-M; i++){
if((mask>>i)&1){
if(last==-1){
lowest=H[i+M];
}
if(H[i+M]<last){
ok=0;
break;
}
last=H[i+M];
sum+=G[i+M];
}
}
if(ok){
for(int i=0;i<=lowest;i++){
// count how many are >= K-sum
ans+=v[i].end()-lower_bound(v[i].begin(),v[i].end(),K-sum);
}
if(sum>=K) ans++;
}
}
cout<<ans<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2020 KB |
Output is correct |
2 |
Correct |
0 ms |
2020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2020 KB |
Output is correct |
2 |
Correct |
0 ms |
2020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
2352 KB |
Output is correct |
2 |
Correct |
3 ms |
2020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
3032 KB |
Output is correct |
2 |
Correct |
19 ms |
2164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
266 ms |
4804 KB |
Output is correct |
2 |
Correct |
126 ms |
3948 KB |
Output is correct |