이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define run ios_base::sync_with_stdio(false);cin.tie(0);
#define ll long long
#define pll pair<ll, ll>
#define ull unsigned ll
#define ld double
#define endl "\n"
#define pb push_back
#define fi first
#define se second
#define pi acos(-1)
#define N 4007
#define minimum -9223372036854775807
#define maximum -minimum
#define mod 1000000007
using namespace std;
using namespace __gnu_pbds;
template <class t>
using ordered_set=tree<t, null_type,less_equal<t>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll gcd(ll a, ll b)
{
if(b==0)
return a;
return gcd(b, a%b);
}
ll lcm(ll a, ll b)
{
return a/gcd(a, b)*b;
}
bool isprime(ll n)
{
if(n==1)
return 0;
for(ll i=2; i*i<=n; i++)
{
if(n%i==0)
return 0;
}
return 1;
}
ll binpow(ll a, ll b)
{
a%=mod;
ll res=1;
while(b>0)
{
if(b%2==1)
res=(res*a)%mod;
a=(a*a)%mod;
b/=2;
}
return res;
}
int main()
{
run;
ll n, k;
cin>>n>>k;
ll a[n];
for(ll i=0; i<n; i++)
{
cin>>a[i];
}
vector<ll>v;
ll sm=0, say=n/2, say2=n-say;
for(ll i=0; i<(1<<say); i++)
{
sm=0;
for(ll j=0; j<say; j++)
{
if((1<<j)&i)
{
sm+=a[j];
}
}
v.pb(sm);
}
sort(v.begin(), v.end());
ll sz=v.size(), cvb=0;
for(ll i=0; i<(1<<say2); i++)
{
sm=0;
for(ll j=0; j<say2; j++)
{
if((1<<j)&i)
{
sm+=a[j+say];
}
}
// cout<<sm<<" ";
ll cur=upper_bound(v.begin(), v.end(), k-sm)-v.begin();
// cout<<cur<<endl;
cvb+=cur;
}
cout<<cvb<<endl;
}
/*
2
1 1 1
1 2 2
3
1 1 1 1
1 1 2 2
1 2 1 3
1 2 2 4
1 2 3 5
4
1 1 1 1 1
1 1 1 2 2
1 1 2 1 3
1 1 2 2 4
1 1 2 3 5
1 2 1 1 6
1 2 1 2 7
1 2 2 1 8
1 2 2 2 9
1 2 2 3 10
1 2 3 2 11
1 2 3 3 12
1 2 3 4 13
1 1 1 1 1 1
1 1 1 1 2 2
1 1 1 2 1 3
1 1 1 2 2 4
1 1 1 2 3 5
1 1 2 1 1 6
1 1 2 1 2 7
1 1 2 2 1 8
1 1 2 2 2 9
1 1 2 2 3 10
1 1 2 3 2 11
1 1 2 3 3 12
1 1 2 3 4 13
1 1 3 2 1
1 1 3 2 2
1 1 3 2 3
1 1 3 3 2
1 1 3 3 3
1 1 3 3 4
1 1 3 4 3
1 1 3 4 4
1 1 3 4 5
1 2 1 1 1
*/
// By Xanlar
컴파일 시 표준 에러 (stderr) 메시지
bobek.cpp: In function 'int main()':
bobek.cpp:91:5: warning: unused variable 'sz' [-Wunused-variable]
91 | ll sz=v.size(), cvb=0;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |