結果

問題 No.3401 Large Knapsack Problem
コンテスト
ユーザー apricity
提出日時 2025-12-09 02:18:34
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 6,982 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,867 ms
コンパイル使用メモリ 249,016 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-09 02:18:41
合計ジャッジ時間 6,808 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void fastio::flush()’:
main.cpp:70:21: warning: ignoring return value of ‘ssize_t write(int, const void*, size_t)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 | void flush() { write(1, obuf, obufi), obufi = 0; }
      |                ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#pragma GCC target("prefer-vector-width=512")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Ofast,unroll-loops")
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<utility>
#include<tuple>
#include<array>
#include<cstdint>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<cctype>
#include<chrono>
#include<random>
#include<cassert>
#include<cstddef>
#include<iterator>
#include<string_view>
#include<type_traits>
#include<functional>

using namespace std;

#include <cstring>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>

namespace fastio {

#ifndef FAST_IO
#define FAST_IO
#endif

struct Pre {
    char num[10000][4];
    constexpr Pre() : num() {
        for (int i = 0; i < 10000; i++) {
            int n = i;
            for (int j = 3; j >= 0; j--) {
                num[i][j] = n % 10 | '0';
                n /= 10;
            }
        }
    }
} constexpr pre;

static constexpr int BUF_SZ = 1 << 18;
char *ibuf, obuf[BUF_SZ], outs[100];
int outi, obufi;

void __attribute__((constructor)) _c() {
    struct stat sb;
    fstat(0, &sb);
    ibuf = (char *)mmap(0, sb.st_size, PROT_READ, MAP_SHARED /*| MAP_POPULATE*/, 0, 0);
}

void flush() { write(1, obuf, obufi), obufi = 0; }

void input(char &c) { c = *ibuf++; }
void input(string &x) {
    x.clear();
    char c;
    do { input(c); } while (isspace(c));
    do { x += c, input(c); } while (!isspace(c));
}

template <typename T>
void input_integer(T &x) {
    char c;
    do { input(c); } while (c < '-');
    bool minus = 0;
    if constexpr (is_signed<T>::value || is_same_v<T, __int128>) {
        if (c == '-') { minus = 1, input(c); }
    }
    x = 0;
    while (c >= '0') { x = x * 10 + (c & 15), input(c); }
    if constexpr (is_signed<T>::value || is_same_v<T, __int128>) {
        if (minus) { x = -x; }
    }
}

template <typename T>
void input_real(T &x) { string s; input(s); x = stod(s); }

void input(int &x) { input_integer(x); }
void input(long long &x) { input_integer(x); }
void input(__int128 &x) { input_integer(x); }
void input(uint32_t &x) { input_integer(x); }
void input(uint64_t &x) { input_integer(x); }
void input(unsigned __int128 &x) { input_integer(x); }
void input(double &x) { input_real(x); }

template <class T>
void input(vector<T> &x) { for (auto &d : x) input(d); }
template <typename T, size_t N = 0>
void input(array<T, N> &x) { for (auto &d : x) input(d); }
template <class T, class U>
void input(pair<T, U> &p) { input(p.first), input(p.second); }
template <size_t N = 0, typename T>
void input_tuple(T &t) {
    if constexpr (N < std::tuple_size<T>::value) {
        auto &x = std::get<N>(t);
        input(x);
        input_tuple<N + 1>(t);
    }
}
template <class... T>
void input(tuple<T...> &tpl) { input_tuple(tpl); }

void in() {}
template <class H, class... T>
void in(H &h, T &... t) { input(h), in(t...); }

void output(const char c) {
    if (obufi == BUF_SZ) flush();
    obuf[obufi++] = c;
}
void output(const string &s) { for (char c : s) output(c); }

template <typename T>
void output_integer(T x) {
    if (obufi > BUF_SZ - 100) flush();
    if (x < 0) { obuf[obufi++] = '-', x = -x; }
    for (outi = 96; x >= 10000; outi -= 4) {
        memcpy(outs + outi, pre.num[x % 10000], 4);
        x /= 10000;
    }
    if (x >= 1000) {
        memcpy(obuf + obufi, pre.num[x], 4);
        obufi += 4;
    }
    else if (x >= 100) {
        memcpy(obuf + obufi, pre.num[x] + 1, 3);
        obufi += 3;
    }
    else if(x >= 10) {
        int q = (x * 103) >> 10;
        obuf[obufi] = q | '0';
        obuf[obufi + 1] = (x - q * 10) | '0';
        obufi += 2;
    }
    else {
        obuf[obufi++] = x | '0';
    }
    memcpy(obuf + obufi, outs + outi + 4, 96 - outi);
    obufi += 96 - outi;
}

template <typename T>
void output_real(T x) {
    ostringstream oss;
    oss << fixed << setprecision(15) << double(x);
    string s = oss.str();
    output(s);
}

void output(int x) { output_integer(x); }
void output(long long x) { output_integer(x); }
void output(__int128 x) { output_integer(x); }
void output(uint32_t x) { output_integer(x); }
void output(uint64_t x) { output_integer(x); }
void output(unsigned __int128 x) { output_integer(x); }
void output(double x) { output_real(x); }
void output(long double x) { output_real(x); }

template <class T>
void output(const vector<T> &val) {
    size_t n = val.size();
    for (size_t i = 0; i < n; i++) {
        if (i) output(' ');
        output(val[i]);
    }
}

template <class T, class U>
void output(const pair<T, U> &val) {
    output(val.first); output(' '); output(val.second);
}
template <size_t N = 0, typename T>
void output_tuple(const T &t) {
    if constexpr (N < std::tuple_size<T>::value) {
        if constexpr (N > 0) { output(' '); }
        const auto x = std::get<N>(t);
        output(x);
        output_tuple<N+1>(t);
    }
}
template <class... T>
void output(tuple<T...> &tpl) { output_tuple(tpl); }
template <class T, size_t N>
void output(const array<T, N> &val) {
    size_t n = val.size();
    for (size_t i = 0; i < n; i++) {
        if (i) output(' ');
        output(val[i]);
    }
}

void out() { output('\n'); }
template <class H, class... T, char sep = ' '>
void out(H &&h, T &&... t) {
    output(h);
    if (sizeof...(T)) output(sep);
    out(t...);
}

void outr() {}
template <class H, class... T>
void outr(H &&h, T &&... t) {
    output(h);
    outr(t...);
}

void __attribute__((destructor)) _d() { flush(); }
} // namespace fastio

using fastio::in;
using fastio::out;
using ll = long long;
constexpr ll INF = 1e18;
int coef[1000], vi[20], wi[20];
ll dp[1000], f[1000], aux1[1000], aux2[1000];

int main() {
    int n, m; in(n, m);
    for (int i = 0; i < n; i++) {
        in(vi[i], wi[i]);
        coef[1000 - wi[i]] = max(coef[1000 - wi[i]], vi[i]);
    }
    for (int x = 1; x < 1000; x++) {
        for (int i = 0; i < n; i++) {
            if (x >= wi[i]) dp[x] = max(dp[x], dp[x - wi[i]] + vi[i]);
        }
    }
    fill_n(f, 1000, -INF);
    f[0] = 0;
    int p = 31 - __builtin_clz(m);
    while (p >= 0) {
        memcpy(aux1, f, sizeof(ll) * 1000);
        memcpy(aux2, f, sizeof(ll) * 1000);
        for (int i = 0; i < 1000; i++) f[i] = aux1[0] + aux2[i];
        for (int i = 1; i < 1000; i++) {
            ll bk = aux2[999];
            for (int j = 999; j >= 1; j--) aux2[j] = max(aux2[j - 1], bk + coef[j]);
            aux2[0] = bk + coef[0];
            for (int j = 0; j < 1000; j++) f[j] = max(f[j], aux1[i] + aux2[j]);
        }
        if (m >> p & 1) {
            ll bk = f[999];
            for (int i = 999; i >= 1; i--) f[i] = max(f[i - 1], bk + coef[i]);
            f[0] = bk + coef[0];
        }
        p--;
    }
    ll ans = 0;
    for (int i = 0; i < 1000; i++) ans = max(ans, f[i] + dp[i]);
    out(ans);
}
0