제출 #1295703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1295703		mahmudisali	Ice Hockey World Championship (CEOI15_bobek)	C++20	100 / 100	444 ms	20908 KiB

bobek

// Designed by Mahmud Isali
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #ifndef ONLINE_JUDGE
// #include "debug.h"
// #else
// #define debug(...)
// #endif

using pii = pair<int,int>;
using dbl = double;

#define int long long
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fastio() ios::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define newl cout << endl
#define spl debug(string(100,'-'))

template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>using ordered_multiset = tree<pair<T,int>, null_type, less<pair<T,int>>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>int sz(const T& x) { return (int)x.size(); }
template<class T>int upper_index(const vector<T> &a, const T &x) {return (int)(upper_bound(all(a), x) - a.begin());}
template<class T>int lower_index(const vector<T> &a, const T &x) {return (int)(lower_bound(all(a), x) - a.begin());}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int  INF  = (int)4e18;
const int  MOD  = 1000000007;
const int  MOD2 = 998244353;
const int  N = 32768;
const dbl  EPS  = 1e-12;
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for(int &x : v) cin >> x;
    vector<int> a,b;
    for (int m = 0; m < (1 << (n / 2)) ; m++){
        int sum=0;
        for (int i = 0;i < (n >> 1);i++){
            if (m & (1 << i))
                sum += v[i];
        }
        if (sum <= k)
            a.pb(sum);
    }
    for (int m = 0;m < (1 << ((n + 1) / 2)) ; m++){
        int sum = 0;
        for (int i = n / 2;i < n;i++){
            if (m & (1 << (i - n / 2)))
                sum += v[i];
        }
        if (sum <= k)
            b.pb(sum);
    }
    int res=0;
    sort(b.begin(), b.end());
    for (auto x : a)
        res += upper_index(b, k - x);
    cout<< res << endl;
        
}

signed main() {
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // freopen("error.txt","w",stderr);
    // #endif
    fastio();
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) {
        // cout << "Test Case: " << i << endl;
        solve();
    }
}
    

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10