#804883 (C++23) No.2093 Shio Ramen

提出ソース

結果

問題	No.2093 Shio Ramen
ユーザー	SnowBeenDiding
提出日時	2022-10-07 21:28:04
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	15 ms / 2,000 ms
コード長	10,652 bytes
コンパイル時間	7,100 ms
コンパイル使用メモリ	335,244 KB
実行使用メモリ	18,944 KB
最終ジャッジ日時	2024-06-12 06:05:27
合計ジャッジ時間	7,003 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	4 ms 5,376 KB
testcase_10	AC	10 ms 13,568 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	3 ms 5,376 KB
testcase_15	AC	8 ms 10,752 KB
testcase_16	AC	4 ms 6,144 KB
testcase_17	AC	3 ms 5,376 KB
testcase_18	AC	14 ms 18,048 KB
testcase_19	AC	9 ms 12,416 KB
testcase_20	AC	6 ms 8,448 KB
testcase_21	AC	7 ms 10,112 KB
testcase_22	AC	6 ms 9,856 KB
testcase_23	AC	14 ms 18,944 KB
testcase_24	AC	14 ms 18,944 KB
testcase_25	AC	14 ms 18,944 KB
testcase_26	AC	13 ms 18,816 KB
testcase_27	AC	14 ms 18,944 KB
testcase_28	AC	14 ms 18,944 KB
testcase_29	AC	15 ms 18,944 KB
testcase_30	AC	14 ms 18,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <atcoder/all>
using namespace atcoder;
// using mint = modint1000000007;
using mint = modint998244353;
// using mint = modint;//mint::set_mod(MOD);

// const long long MOD = 1000000007;
const long long MOD = 998244353;

#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 each(a, b) for (auto &(a) : (b))
#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 mp make_pair
#define mt make_tuple
#define tget(a, b) get<b>(a)
#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;

/* print */
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &V) {
    int N = V.size();
    if (N == 0) {
        os << endl;
        return os;
    }
    rep(i, 0, N - 1) { os << V[i] << ' '; }
    os << V[N - 1] << endl;
    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.FI << ' ' << P.SE;
    return os;
}
ostream &operator<<(ostream &os, mint const &M) {
    os << M.val();
    return os;
}

/* useful */
template <typename T>
void Vin(vector<T> &v) {
    int n = v.size();
    rep(i, 0, n) cin >> v[i];
}
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)); }

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)));
// for (auto p : se ) {}

/********************************** START **********************************/

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, m;
    cin >> n >> m;
    Vi s(n), a(n);
    rep(i, 0, n) cin >> s[i] >> a[i];
    knapsack ks;
    rep(i, 0, n) ks.add_goods(a[i], s[i]);
    // rep(i, 0, 10) {
    //     cout << ks.solve(i) << endl;
    // }
    auto ans = ks.solve(m);
    cout << ans;
}

int main() {
    init();
    int q = 1;
    // cin >> q;
    while (q--) sol();
    return 0;
}

yukicoder

結果

テストケース

ソースコード