이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define int long long
#define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e18 + 9;
const int MAX = 3e5 + 5, LOGMAX = 20, B = 441, MOD = 998244353;
void solve(){
int n, m; cin >> n >> m;
int arr[n + 1];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
map<int, int> mp;
int p1 = n / 2;
int p2 = n - p1;
for(int mask = 0; mask < (1 << p1); mask++){
int sum = 0;
for(int i = 0; i < p1; i++){
if((1 << i) & mask) sum += arr[i];
}
mp[sum]++;
}
vector<pii> v;
int p = 0;
for(auto &a : mp){
p += a.second;
v.push_back({a.first, p});
}
int ans = 0;
for(int mask = 0; mask < (1 << p2); mask++){
int sum = 0;
for(int i = 0; i < p2; i++){
if((1 << i) & mask) sum += arr[p1 + i];
}
if(sum > m) continue;
ans += (upper_bound(all(v), make_pair(m - sum, oo)) - 1)->second;
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
}
# | 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... |