結果

問題 No.2232 Miser's Gift
ユーザー GEX777
提出日時 2023-03-04 20:00:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 15,496 bytes
コンパイル時間 1,849 ms
コンパイル使用メモリ 142,612 KB
実行使用メモリ 83,328 KB
最終ジャッジ日時 2024-09-18 01:23:23
合計ジャッジ時間 11,366 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

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

// 2023-02-21 update
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <sstream>
#include <climits>
#include <bitset>
#include <deque>
#include <cassert>
#include <list>
#include <queue>
#include <array>
#include <valarray>
#include <complex>
#include <bitset>
#include <random>
using namespace std;
// 独自型定義
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
using AdjacencyList = map<int, vi>;
using EdgeAdjacencyList = map<int, vector<int, int>>;
// マクロの宣言
#define all(x) x.begin(), x.end()
// 定数宣言
constexpr double PI = 3.141592653589793;
constexpr ll MOD998 = 998244353;
constexpr ll MOD107 = 1'000'000'007;
/****************************************************
*************ここから下は自作ライブラリ**************
****************************************************/
// コンテナの中身を表示, 1行で出力をする, debug用
template <typename T>
void printv(T &a)
{
    for (const auto &x : a)
    {
        cout << x << " ";
    }
    puts("");
    return;
}
// コンテナの中身を表示, 二次元配列用
template <typename T>
void printvv(T &a)
{
    for (const auto &x : a)
    {
        printv(x);
    }
}
// コンテナの中身を表示, pair型
template <typename T>
void print_vpair(const T &a)
{
    for (const auto &x : a)
    {
        cout << "(" << x.first << ", " << x.second << "), ";
    }
    puts("");
    return;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
// コンテナの中身を表示, 改行して出力をする, debug用
template <typename T>
void println(T &a)
{
    for (const auto &x : a)
    {
        cout << x << endl;
    }
    return;
}
// 1~Nまでの総和を求める
ll sum_from_1_to_N(ll N)
{
    if (N < 1LL)
    {
        return 0;
    }
    if ((N & 1) == 0) // even
    {
        return N / 2 * (N + 1);
    }
    else // odd
    {
        return (N + 1) / 2 * N;
    }
}
// A~Nまでの総和を求める
ll sum_from_A_to_B(ll A, ll B)
{
    return sum_from_1_to_N(B) - sum_from_1_to_N(A);
}
// a^bを求める, 繰り返し2乗法を用いる,3番目の引数はModを取る場合に設定
ll intPowMod(ll a, ll b, const ll MOD = LLONG_MAX)
{
    ll ans = 1;
    ll A = a;
    while (b > 0)
    {
        int n = b % 2;
        b /= 2;
        if (n == 1)
        {
            ans *= A % MOD;
            ans %= MOD;
        }
        A = ((A % MOD) * (A % MOD)) % MOD;
    }
    return ans;
}
ld arg_to_rad(ld arg)
{
    return (arg * PI / 180.0);
}
ld rad_to_arg(ld rad)
{
    return rad * 180.0 / PI;
}
// C(n, m)を求める
ll combination(const ll n, const ll m)
{
    assert(n >= m); // n>=mは保証される
    ll up = 1;
    ll down = 1;
    for (int i = n; i > n - m; i--)
    {
        up *= i;
    }
    for (int i = m; i >= 2; i--)
    {
        down *= i;
    }
    return up / down;
}
// 動的計画法で前処理,O(N**2)
vvll combination_table(const int MAX_N = 50)
{
    vvll com = vvll(MAX_N + 1, vll(MAX_N + 1, 0)); // 前計算の結果を保存
    com[0][0] = 1;
    for (int i = 1; i <= MAX_N; ++i)
    {
        com[i][0] = 1;
        for (int j = 1; j <= MAX_N; j++)
        {
            com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]);
        }
    }
    return com;
}
// a÷bをMODで割ったあまりを返す関数
ll DivisionMod(ll a, ll b, ll MOD)
{
    return (a * intPowMod(b, MOD - 2, MOD)) % MOD;
}
// C(n, r)をModで割った余りを返す関数, 3番めの引数を入れないと通常のConbination
ll combinationMod(ll n, ll r, ll MOD = LLONG_MAX)
{
    // 分子upを求める
    ll up = 1;
    for (ll i = n - r + 1; i <= n; ++i)
    {
        up = (up * i) % MOD;
    }
    // 分母downを求める
    ll down = 1;
    for (ll i = 1; i <= r; ++i)
        down = (down * i) % MOD;
    return DivisionMod(up, down, MOD);
}
// a,bの最大公約数を求める, A>=B>=0の時, 計算量O(logB)
long long GCD(long long a, long long b)
{
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
// 最小公倍数
ll LCM(ll a, ll b)
{
    return a * b / GCD(a, b);
}
// 素数判定, P->true, not_P->false
bool check_Prime(ll N)
{
    if (N == 2)
        return true;
    if (N == 1 || (N & 1) == 0)
        return false;
    for (ll i = 3; i <= sqrt(N); i += 2)
    {
        if (N % i == 0)
            return false;
    }
    return true;
}
// 素因数分解,key:素数, value:指数のmap<ll,ll>を返す
map<ll, ll> prime_factorize(ll number)
{
    map<ll, ll> table;
    for (ll i = 2; i * i <= number; ++i)
    {
        while (number % i == 0)
        {
            table[i]++;
            number /= i;
        }
    }
    if (number != 1LL)
    {
        table[number]++;
    }
    return table;
}
/* エラストステネス and 高速素因数分解
   prime->IsPrime[i]=i; not prime ->最小の素因数 */
vi Eratosthenes(size_t max_number)
{
    vi IsPrime(max_number + 1);
    // tableの初期化
    for (int i = 1; i < IsPrime.size(); ++i)
    {
        IsPrime[i] = i;
    }
    for (int i = 2; i <= sqrt(max_number); ++i)
    {
        for (int j = i; j <= max_number; j += i)
        {
            if (IsPrime[j] == j)
            {
                IsPrime[j] = i;
            }
        }
    }
    return IsPrime;
}
// O(N)でNの階乗を求める
ll factorial(const ll N)
{
    ll ans = 1;
    for (ll i = 1; i <= N; ++i)
    {
        ans *= i;
    }
    return ans;
}
// Run Length Encoding, ランレングス圧縮
template <typename T>
vector<pair<T, int>> RLE(const vector<T> &A)
{
    vector<pair<T, int>> rle;
    rle.push_back({A.front(), 1});
    for (int i = 1; i < A.size(); ++i)
    {
        if (rle.back().first == A[i])
        {
            rle.back().second++;
        }
        else
        {
            rle.push_back({A[i], 1});
        }
    }
    return rle;
}
vector<pair<char, int>> RLE(const string &S)
{
    vector<pair<char, int>> rle;
    rle.push_back({S.front(), 1});
    for (int i = 1; i < S.size(); ++i)
    {
        if (rle.back().first == S[i])
        {
            rle.back().second++;
        }
        else
        {
            rle.push_back({S[i], 1});
        }
    }
    return rle;
}
void DEBUG_INDICATE()
{
    static int cnt = 0;
    cout << "-----DEBUG: " << cnt++ << "------" << endl;
    return;
}
void DEBUG_INDICATE(const string message)
{
    cout << "-----DEBUG: " << message << "------" << endl;
    return;
}
/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
    update(i,x): i 番目の要素を x に更新。O(log(n))
    query(a,b): [a,b) での最小の要素を取得。O(log(n))
*/
template <typename T>
struct RangeMinimumQuery
{
    const T INF = numeric_limits<T>::max();
    int n;         // 葉の数
    vector<T> dat; // 完全二分木の配列
    RangeMinimumQuery(int n_) : n(), dat(n_ * 4, INF)
    { // 葉の数は 2^x の形
        int x = 1;
        while (n_ > x)
        {
            x *= 2;
        }
        n = x;
    }
    void update(int i, T x)
    {
        i += n - 1;
        dat[i] = x;
        while (i > 0)
        {
            i = (i - 1) / 2; // parent
            dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
    // the minimum element of [a,b)
    T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
    T query_sub(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l)
        {
            return INF;
        }
        else if (a <= l && r <= b)
        {
            return dat[k];
        }
        else
        {
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
};
/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
    update(i,x): i 番目の要素を x に更新。O(log(n))
    query(a,b): [a,b) での最小の要素を取得。O(log(n))
*/
template <typename T>
struct RangeMaximumQuery
{
    const T INF = numeric_limits<T>::min();
    int n;         // 葉の数
    vector<T> dat; // 完全二分木の配列
    RangeMaximumQuery(int n_) : n(), dat(n_ * 4, INF)
    { // 葉の数は 2^x の形
        int x = 1;
        while (n_ > x)
        {
            x *= 2;
        }
        n = x;
    }
    void update(int i, T x)
    {
        i += n - 1;
        dat[i] = x;
        while (i > 0)
        {
            i = (i - 1) / 2; // parent
            dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
    // the minimum element of [a,b)
    T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
    T query_sub(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l)
        {
            return INF;
        }
        else if (a <= l && r <= b)
        {
            return dat[k];
        }
        else
        {
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return max(vl, vr);
        }
    }
};
// Union-Find
struct UnionFind
{
    vector<int> par, rank, siz;
    // 構造体の初期化
    UnionFind(int n) : par(n, -1), rank(n, 0), siz(n, 1) {}
    // 根を求める
    int root(int x)
    {
        if (par[x] == -1)
            return x; // x が根の場合は x を返す
        else
            return par[x] = root(par[x]); // 経路圧縮
    }
    // x と y が同じグループに属するか (= 根が一致するか)
    bool issame(int x, int y)
    {
        return root(x) == root(y);
    }
    // x を含むグループと y を含むグループを併合する
    bool unite(int x, int y)
    {
        int rx = root(x), ry = root(y); // x 側と y 側の根を取得する
        if (rx == ry)
            return false; // すでに同じグループのときは何もしない
        // union by rank
        if (rank[rx] < rank[ry])
            swap(rx, ry); // ry 側の rank が小さくなるようにする
        par[ry] = rx;     // ry を rx の子とする
        if (rank[rx] == rank[ry])
            rank[rx]++;     // rx 側の rank を調整する
        siz[rx] += siz[ry]; // rx 側の siz を調整する
        return true;
    }
    // x を含む根付き木のサイズを求める
    int size(int x)
    {
        return siz[root(x)];
    }
};
/* BIT: 区間和の更新や計算を行う構造体
初期値は a_1 = a_2 = ... = a_n = 0
計算量は全て O(logn)
*/
template <typename T>
struct BIT
{
    int n;         // 配列の要素数(数列の要素数+1)
    vector<T> bit; // データの格納先
    // 構造体の初期化
    BIT(int n_) : n(n_ + 1), bit(n, 0) {}
    // add(i,x): a_i += x とする
    void add(int i, T x)
    {
        for (int idx = i; idx < n; idx += (idx & -idx))
        {
            bit[idx] += x;
        }
    }
    // sum(i): a_1 + a_2 + ... + a_i を計算する
    T sum(int i)
    {
        T s(0);
        for (int idx = i; idx > 0; idx -= (idx & -idx))
        {
            s += bit[idx];
        }
        return s;
    }
};
/*********************************************
*************ライブラリ終わり******************
***********************************************/
template <unsigned mod>
struct RollingHash
{
    vector<unsigned> hashed, power;
    inline unsigned mul(unsigned a, unsigned b) const
    {
        unsigned long long x = (unsigned long long)a * b;
        unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
        asm("divl %4; \n\t"
            : "=a"(d), "=d"(m)
            : "d"(xh), "a"(xl), "r"(mod));
        return m;
    }
    RollingHash(const string &s, unsigned base = 10007)
    {
        int sz = (int)s.size();
        hashed.assign(sz + 1, 0);
        power.assign(sz + 1, 0);
        power[0] = 1;
        for (int i = 0; i < sz; i++)
        {
            power[i + 1] = mul(power[i], base);
            hashed[i + 1] = mul(hashed[i], base) + s[i];
            if (hashed[i + 1] >= mod)
                hashed[i + 1] -= mod;
        }
    }
    unsigned get(int l, int r) const
    {
        unsigned ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
        if (ret >= mod)
            ret -= mod;
        return ret;
    }
    unsigned connect(unsigned h1, int h2, int h2len) const
    {
        unsigned ret = mul(h1, power[h2len]) + h2;
        if (ret >= mod)
            ret -= mod;
        return ret;
    }
    int LCP(const RollingHash<mod> &b, int l1, int r1, int l2, int r2)
    {
        int len = min(r1 - l1, r2 - l2);
        int low = -1, high = len + 1;
        while (high - low > 1)
        {
            int mid = (low + high) / 2;
            if (get(l1, l1 + mid) == b.get(l2, l2 + mid))
                low = mid;
            else
                high = mid;
        }
        return (low);
    }
};
ll solve()
{
    ll N;
    cin >> N;
    string S;
    cin >> S;
    // std::random_device rnd;
    RollingHash<998244353> rh(S);
    RollingHash<998244353> rh2(S);
    // RH rh(S);
    set<ll> A, A2;
    for (int i = 0; i <= S.size() - 2; ++i)
    {
        // cout << 0 << ", i=" << i << " || i+2=" << i+2 << " R=" << S.size() << endl;
        auto L = rh.get(0, i);
        auto R = rh.get(i + 2, S.size());
        int len = S.size() - (i + 2);
        auto s = rh.connect(L, R, len);
        // cout << "L=" << L << " R=" << R << " s=" << s <<" len=" <<len << endl;
        A.insert(s);
        // cout << 0 << ", i=" << i << " || i+2=" << i+2 << " R=" << S.size() << endl;
        auto L2 = rh2.get(0, i);
        auto R2 = rh2.get(i + 2, S.size());
        // int len2 = S.size() - (i + 2);
        auto s2 = rh2.connect(L, R, len);
        // cout << "L=" << L << " R=" << R << " s=" << s <<" len=" <<len << endl;
        A2.insert(s);
    }
    // std::random_device rnd;
    // RH rh(S);
    return max(A.size(), A2.size());
}
int main()
{
    int N, W_MAX;
    cin >> N >> W_MAX;
    vll W(N), V(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> W[i] >> V[i];
    }
    vvll dp(N + 1, vll(W_MAX + 1, -1));
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j <= W_MAX; ++j)
        {
            if (dp[i][j] == -1)
                continue;
            if (j + W[i] <= W_MAX)
            {
                chmax(dp[i + 1][j + W[i]], dp[i][j] + V[i]);
            }
            chmax(dp[i + 1][j], dp[i][j]);
        }
    }
    for(int i=1; i<=W_MAX; ++i)
    {
        chmax(dp.back()[i], dp.back()[i-1]);
    }
    // DEBUG_INDICATE("DP.back()");
    // printv(dp.back());
    for (int i = 1; i <= W_MAX; ++i)
    {
        cout << dp.back()[W_MAX] - dp.back()[W_MAX-i] + 1<< endl;
        // cout << ans + 1 << endl;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0