結果
問題 | No.2730 Two Types Luggage |
ユーザー |
![]() |
提出日時 | 2024-04-19 21:33:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 683 ms / 2,000 ms |
コード長 | 3,030 bytes |
コンパイル時間 | 2,039 ms |
コンパイル使用メモリ | 202,060 KB |
最終ジャッジ日時 | 2025-02-21 03:49:40 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 1e9 + 10;const ll INFL = 4e18;template <ll MOD>struct modint {ll value;modint(ll x = 0) {if (x >= 0) {value = x % MOD;} else {value = MOD - (-x) % MOD;}}modint operator-() const {return modint(-value);}modint operator+() const {return modint(*this);}modint &operator+=(const modint &other) {value += other.value;if (value >= MOD) {value -= MOD;}return *this;}modint &operator-=(const modint &other) {value += MOD - other.value;if (value >= MOD) {value -= MOD;}return *this;}modint &operator*=(const modint other) {value = value * other.value % MOD;return *this;}modint &operator/=(modint other) {(*this) *= other.inv();return *this;}modint operator+(const modint &other) const {return modint(*this) += other;}modint operator-(const modint &other) const {return modint(*this) -= other;}modint operator*(const modint &other) const {return modint(*this) *= other;}modint operator/(const modint &other) const {return modint(*this) /= other;}modint pow(ll x) const {modint ret(1), mul(value);while (x) {if (x & 1) {ret *= mul;}mul *= mul;x >>= 1;}return ret;}modint inv() const {return pow(MOD - 2);}bool operator==(const modint &other) const {return value == other.value;}bool operator!=(const modint &other) const {return value != other.value;}friend ostream &operator<<(ostream &os, const modint &x) {return os << x.value;}friend istream &operator>>(istream &is, modint &x) {ll v;is >> v;x = modint<MOD>(v);return is;}};using mod998 = modint<998244353>;using mod107 = modint<1000000007>;using mint = mod998;int main() {int N, M;ll W;cin >> N >> M >> W;vector<ll> A(N), B(M), C(M);for (int i = 0; i < N; i++) {cin >> A[i];}for (int i = 0; i < M; i++) {cin >> B[i];}for (int i = 0; i < M; i++) {cin >> C[i];}sort(A.rbegin(), A.rend());vector<ll> sumA(N + 1, 0);for (int i = 0; i < N; i++) {sumA[i + 1] = sumA[i] + A[i];}ll ans = 0;for (int i = 0; i < 1 << M; i++) {ll weight = 0, value = 0;for (int j = 0; j < M; j++) {if (i >> j & 1) {weight += B[j];value += C[j];}}if (weight > W) {continue;}value += sumA[min<ll>(N, W - weight)];ans = max(ans, value);}cout << ans << endl;}