結果

問題 No.2232 Miser's Gift
ユーザー SnowBeenDiding
提出日時 2023-03-03 21:39:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 143 ms / 2,000 ms
コード長 12,301 bytes
コンパイル時間 5,733 ms
コンパイル使用メモリ 323,984 KB
実行使用メモリ 162,108 KB
最終ジャッジ日時 2024-09-17 22:33:45
合計ジャッジ時間 11,304 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 55
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'll knapsack::solve(ll)':
main.cpp:433:5: warning: control reaches end of non-void function [-Wreturn-type]
  433 |     }
      |     ^

ソースコード

diff #
プレゼンテーションモードにする

#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
const long long MOD = 998244353;
// using mint = modint1000000007;
// const long long MOD = 1000000007;
// using mint = modint;//mint::set_mod(MOD);
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define repeq(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); i++)
#define repreq(i, a, b) for (ll i = (ll)(a); i >= (ll)(b); i--)
#define endl '\n'  // fflush(stdout);
#define cYes cout << "Yes" << endl
#define cNo cout << "No" << endl
#define sortr(v) sort(v, greater<>())
#define pb push_back
#define pob pop_back
#define mp make_pair
#define mt make_tuple
#define FI first
#define SE second
#define ALL(v) (v).begin(), (v).end()
#define INFLL 3000000000000000100LL
#define INF 1000000100
#define PI acos(-1.0L)
#define TAU (PI * 2.0L)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> Pll;
typedef tuple<ll, ll, ll> Tlll;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<ll> Vl;
typedef vector<Vl> VVl;
typedef vector<VVl> VVVl;
typedef vector<Tlll> VTlll;
typedef vector<mint> Vm;
typedef vector<Vm> VVm;
typedef vector<string> Vs;
typedef vector<double> Vd;
typedef vector<char> Vc;
typedef vector<bool> Vb;
typedef vector<Pll> VPll;
typedef priority_queue<ll> PQl;
typedef priority_queue<ll, vector<ll>, greater<ll>> PQlr;
/* inout */
ostream &operator<<(ostream &os, mint const &m) {
    os << m.val();
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    int n = v.size();
    rep(i, 0, n) { os << v[i] << " \n"[i == n - 1]; }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
    int n = v.size();
    rep(i, 0, n) os << v[i];
    return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> const &p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &mp) {
    for (auto &[key, val] : mp) {
        os << key << ':' << val << '\n';
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st) {
    auto itr = st.begin();
    for (int i = 0; i < (int)st.size(); i++) {
        os << *itr << (i + 1 != (int)st.size() ? ' ' : '\n');
        itr++;
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, multiset<T> &st) {
    auto itr = st.begin();
    for (int i = 0; i < (int)st.size(); i++) {
        os << *itr << (i + 1 != (int)st.size() ? ' ' : '\n');
        itr++;
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, queue<T> q) {
    while (q.size()) {
        os << q.front();
        q.pop();
        os << " \n"[q.empty()];
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, stack<T> st) {
    vector<T> v;
    while (st.size()) {
        v.push_back(st.top());
        st.pop();
    }
    reverse(ALL(v));
    os << v;
    return os;
}
template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) {
    vector<T> v;
    while (pq.size()) {
        v.push_back(pq.top());
        pq.pop();
    }
    os << v;
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &in : v) is >> in;
    return is;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}
/* useful */
template <typename T>
int SMALLER(vector<T> &a, T x) {
    return lower_bound(a.begin(), a.end(), x) - a.begin();
}
template <typename T>
int orSMALLER(vector<T> &a, T x) {
    return upper_bound(a.begin(), a.end(), x) - a.begin();
}
template <typename T>
int BIGGER(vector<T> &a, T x) {
    return a.size() - orSMALLER(a, x);
}
template <typename T>
int orBIGGER(vector<T> &a, T x) {
    return a.size() - SMALLER(a, x);
}
template <typename T>
int COUNT(vector<T> &a, T x) {
    return upper_bound(ALL(a), x) - lower_bound(ALL(a), x);
}
template <typename T, typename S>
bool chmax(T &a, S b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T, typename S>
bool chmin(T &a, S b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
void press(T &v) {
    v.erase(unique(ALL(v)), v.end());
}
template <typename T>
vector<int> zip(vector<T> b) {
    pair<T, int> p[b.size() + 10];
    int a = b.size();
    vector<int> l(a);
    for (int i = 0; i < a; i++) p[i] = mp(b[i], i);
    sort(p, p + a);
    int w = 0;
    for (int i = 0; i < a; i++) {
        if (i && p[i].first != p[i - 1].first) w++;
        l[p[i].second] = w;
    }
    return l;
}
template <typename T>
vector<T> vis(vector<T> &v) {
    vector<T> S(v.size() + 1);
    rep(i, 1, S.size()) S[i] += v[i - 1] + S[i - 1];
    return S;
}
ll dem(ll a, ll b) { return ((a + b - 1) / (b)); }
ll dtoll(double d, int g) { return round(d * pow(10, g)); }
string tobin(ll n, ll d) {
    string ret;
    rep(i, 0, d) {
        ret += (n % 2) ? '1' : '0';
        n /= 2;
    }
    reverse(ALL(ret));
    return ret;
}
const double EPS = 1e-10;
void init() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(12);
}
// do {} while (next_permutation(ALL(vec)));
/********************************** START **********************************/
void sol();
int main() {
    init();
    int q = 1;
    // cin >> q;
    while (q--) sol();
    return 0;
}
/********************************** SOLVE **********************************/
struct knapsack {
    ll N, W, ans;
    vector<pair<ll, ll>> goods;  // (価値，重さ)
    vector<vector<ll>> dp;
    ll max_w, max_v, sum_v;  // 品物に関する最大値
    knapsack() { init(); }
    void init() {
        N = 0;
        max_w = -INF;
        max_v = -INF;
        sum_v = 0;
        ans = 0;
    }
    void add_goods(ll v, ll w) {
        N++;
        goods.push_back(make_pair(v, w));
        max_w = max(max_w, w);
        max_v = max(max_v, v);
        sum_v += v;
    }
    ll lorry() {  // https://codeforces.com/contest/3/problem/B
        ans = 0;
        ll now_W = W;
        vector<pair<ll, ll>> one, two;
        rep(i, 0, N) {
            if (goods[i].second == 1)
                one.push_back(mp(goods[i].first, i));
            else
                two.push_back(mp(goods[i].first, i));
        }
        rep(i, 0, 5) one.pb(mp(0, INF));
        rep(i, 0, 5) two.pb(mp(0, INF));
        sort(ALL(one));
        sort(ALL(two));
        ll ol = one.size() - 1, tl = two.size() - 1;
        while (1) {
            ll os, ts;
            if (now_W == 0) break;
            os = one[ol].first + one[ol - 1].first;
            ts = two[tl].first;
            if (ts == 0 && os == 0) break;
            if (now_W == 1) {
                now_W--;
                ans += one[ol].first;
                ol--;
                break;
            }
            if (os <= ts) {
                ans += ts;
                tl--;
                now_W -= 2;
            } else {
                ans += one[ol].first;
                ol--;
                now_W--;
            }
            if (now_W == 0) break;
        }
        return ans;
    }
    ll
    small_W() {  // https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_B
        dp = vector<vector<ll>>(N + 1, vector<ll>(W + 1));
        vector<vector<ll>> pre(N + 1, vector<ll>(W + 1, -1));
        rep(i, 0, N) repeq(j, 0, W) {
            if (j >= goods[i].SE) {
                dp[i + 1][j] =
                    max(dp[i][j - goods[i].SE] + goods[i].FI, dp[i][j]);
                if (dp[i][j - goods[i].SE] + goods[i].FI == dp[i + 1][j])
                    pre[i + 1][j] = j - goods[i].SE;
            } else
                dp[i + 1][j] = dp[i][j];
        }
        ll now = W, ii = N;
        while (ii > 0) {
            if (pre[ii][now] == -1) {
                ii--;
                continue;
            } else {
                now = pre[ii][now];
                ii--;
            }
        }
        return dp[N][W];
    }
    ll
    small_V() {  // https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_F
        dp = vector<vector<ll>>(N + 1, vector<ll>(sum_v + 1, INF));
        vector<vector<ll>> pre(N + 1, vector<ll>(sum_v + 1, -1));
        dp[0][0] = 0;
        rep(i, 0, N) repeq(j, 0, sum_v) {
            if (j - goods[i].FI >= 0) {
                dp[i + 1][j] =
                    min(dp[i][j], dp[i][j - goods[i].FI] + goods[i].SE);
                if (dp[i + 1][j] == dp[i][j - goods[i].FI] + goods[i].SE)
                    pre[i + 1][j] = j - goods[i].FI;
            } else
                dp[i + 1][j] = dp[i][j];
        }
        ll ret = 0;
        repeq(i, 0, sum_v) if (dp[N][i] <= W) ret = max(ret, i);
        ll now = ret, ii = N;
        while (ii > 0) {
            if (pre[ii][now] == -1) {
                ii--;
                continue;
            } else {
                now = pre[ii][now];
                ii--;
            }
        }
        return ret;
    }
    ll small_N() {
        ll n1 = N / 2, n2 = N - n1;
        vector<tuple<ll, ll>> ps1, ps2, ps3;
        rep(i, 0, (1 << n1)) {
            ll qw = 0, er = 0;
            rep(j, 0, n1) if (i & (1 << j)) {
                qw += goods[j].FI, er += goods[j].SE;
            }
            ps1.push_back(mt(er, qw));
        }
        rep(i, 0, (1 << n2)) {
            ll qw = 0, er = 0;
            rep(j, 0, n2) if (i & (1 << j)) {
                qw += goods[j + n1].FI, er += goods[j + n1].SE;
            }
            ps2.push_back(mt(er, qw));
        }
        sort(ALL(ps2));
        ps3.push_back(ps2[0]);
        ll maxx = 0;
        vector<ll> ps3_w;
        rep(i, 0, ps2.size()) {
            if (maxx < get<1>(ps2[i])) {
                maxx = get<1>(ps2[i]);
                if (get<0>(ps3.back()) < get<0>(ps2[i]))
                    ps3.push_back(ps2[i]);
                else
                    ps3.back() = ps2[i];
            }
        }
        rep(i, 0, ps3.size()) ps3_w.push_back(get<0>(ps3[i]));
        ll ans = 0;
        rep(i, 0, ps1.size()) {
            ll pre = 0;
            if (W < get<0>(ps1[i])) continue;
            pre += get<1>(ps1[i]);
            ll j = orSMALLER(ps3_w, W - get<0>(ps1[i])) - 1;
            pre += get<1>(ps3[j]);
            if (ans < pre) {
                ans = pre;
            }
        }
        return ans;
    }
    ll cleaning() {  // https://codeforces.com/contest/1475/problem/D
        vector<ll> one, two;
        ll ret = 0;
        rep(i, 0, N) {
            if (goods[i].first == 1)
                one.push_back(goods[i].second);
            else if (goods[i].first == 2)
                two.push_back(goods[i].second);
        }
        sort(ALL(one));
        sort(ALL(two));
        vector<long long> one_sum(1, 0), two_sum(1, 0);
        rep(i, 0, one.size()) one_sum.push_back(one_sum[i] + one[i]);
        rep(i, 0, two.size()) two_sum.push_back(two_sum[i] + two[i]);
        rep(i, 0, one_sum.size()) {
            if (one_sum[i] > W) break;
            ll tmp = orSMALLER(two_sum, (ll)(W - one_sum[i]));
            ll C = (tmp - 1) * 2 + i;
            chmax(ret, C);
        }
        return ret;
    }
    ll solve(ll w) {
        W = w;
        // if (max_w <= 2) return lorry();               // O(N)
        // if (max_v <= 2) return cleaning();            // O(NlogN)
        if (N * W <= 20000100) return small_W();  // O(NW)
        // if (N * sum_v <= 20000100) return small_V();  // O(N * SUM_v)
        // if (N <= 40) return small_N();  // O(M log M) (M = 2^(N/2))
        // return -1;
    }
    /* 使い方 */
    /*
    knapsack KS        // 宣言
    KS.add_goods(w, v) // 品物の追加(重さ, 価値)
    KS.solve(W)        // 容量 W のときの ans を返す
    */
};
void sol() {
    int n, w;
    cin >> n >> w;
    knapsack ks;
    rep(i, 0, n) {
        int qw, er;
        cin >> qw >> er;
        swap(qw, er);
        ks.add_goods(qw, er);
    }
    ks.solve(w);
    auto v = ks.dp.back();
    reverse(ALL(v));
    rep(i, 1, v.size()) { cout << abs(v[0] - v[i]) + 1 << endl; }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0