Submission #2550773

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <iomanip>
#include <numeric>
#include <functional>
#include <queue>
#include <tuple>
#include <map>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vb = vector<char>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) {
    for (auto &e:t) fill_v(e, v);
}

#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define RREP(i, a, b) for (int i = (int)(b) - 1; i >= a; i--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, 0, n)
#define all(x) (x).begin(),(x).end()
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define mp(a, b) make_pair(a,b)

#define fi first
#define sn second
#define decpii(p) p.fi--,p.sn--;


#ifdef LOCAL
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define dumpn(c) cerr << "> " << #c << " = " << (c) << ", ";
#else
#define dump(c) ;
#define dumpn(c) ;
#endif


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
    os << '[';
    rep(i, (int) a.size())os << (i ? " " : "") << a[i];
    return os << ']';
}


const int INF = 1 << 29;
const int MOD = 1000000007;

int dxf[] = {1, 0, -1, 0};
int dyf[] = {0, -1, 0, 1};

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

inline vi uni(vi &vec) {
    sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

struct ____ {
    ____() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
    };
} ________;


ll solve() {
    ll N, W;
    cin >> N >> W;

    vi v(N, 0), w(N, 0);
    rep(i, N)cin >> v[i] >> w[i];
    ll mxv = *max_element(all(v));
    ll mxw = *max_element(all(w));

    if (N <= 30) {
        int s2 = N / 2;
        int s1 = N - s2;

        vector<pll> b1(1 << s1), b2(1 << s2);
        rep(M, 1 << s1) {
            pll wv = mp(0, 0);
            rep(i, s1) {
                if (((M >> i) & 1) == 1) {
                    wv.fi += w[i];
                    wv.sn += v[i];
                }
            }
            b1[M] = wv;
        }
        rep(M, 1 << s2) {
            pll wv = mp(0, 0);
            rep(i, s2) {
                if (((M >> i) & 1) == 1) {
                    wv.fi += w[i+s1];
                    wv.sn += v[i+s1];
                }
            }
            b2[M] = wv;
        }

//        dumpn(b1); dump(b2);

        sort(all(b2));
        ll b2_mxv = 0;
        tr(it,b2) {
            chmax(b2_mxv, it->second);
            it->second = b2_mxv;
        }
//        dump(b2);
        ll max_v = 0;
        tr(it, b1) {
            if(it->first > W) continue;
            ll v = it->second;
            ll tw = W - (it->first);
            auto u = upper_bound(all(b2), mp(tw, 1ll<<50));
//            dumpn(u != begin(b2));
            if (u != begin(b2)) {
                --u;
                v += u->second;
            }
//            dumpn(tw);
//            dumpn(*it);
//            dumpn(*u);
//            dump(v);
            chmax(max_v, v);
        }
        return max_v;
    } else if (mxv <= 1000) {

    } else {

    }

    return -1LL;
}


int main() {
//    cout << (solve() ? "yes" : "no") << endl;
    cout << solve() << endl;
//    solve();
    return 0;
}

Submission Info

Judge Result