結果

問題 No.2730 Two Types Luggage
ユーザー zatsu308
提出日時 2024-04-19 21:33:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 279 ms / 2,000 ms
コード長 1,679 bytes
コンパイル時間 1,840 ms
コンパイル使用メモリ 172,860 KB
実行使用メモリ 18,688 KB
最終ジャッジ日時 2024-10-11 14:15:04
合計ジャッジ時間 8,271 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 998244353;
template<ll mod>
struct Mint {
using M=Mint; ll v;
M& put(ll x) { v=(x<mod)?x:x-mod; return *this; }
Mint(ll x=0) { put(x%mod+mod); }
M operator+(M m) {return M().put(v+m.v);}
M operator-(M m) {return M().put(v+mod-m.v);}
M operator*(M m) {return M().put(v*m.v%mod);}
M operator/(M m) {return M().put(v*m.inv().v%mod);}
// BEGIN IGNORE
M operator+=(M m) { return put(v+m.v); }
M operator-=(M m) { return put(v+mod-m.v); }
M operator*=(M m) { return put(v*m.v%mod); }
M operator/=(M m) { return put(v*m.inv().v%mod); }
// END IGNORE
bool operator==(M m) { return v==m.v; }
M pow(ll m) const {
M x=v, res=1;
while (m) {
if (m&1) res=res*x;
x=x*x; m>>=1;
}
return res;
}
M inv() { return pow(mod-2); }
};
using mint = Mint<mod>;
int main(){
cin.tie(0);
cin.sync_with_stdio(0);
ll n, m, 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 j = 0; j < m; ++j){
cin >> b[j];
}
for(int i = 0; i < m; ++i){
cin >> c[i];
}
ll ans = 0;
sort(a.begin(), a.end(), greater<>());
vector<ll> r(n + 1);
for(int i = 0; i < n; ++i){
r[i + 1] = r[i] + a[i];
}
auto add = [&](ll rem){
if(rem < r.size()){
return r[rem];
}
else return r.back();
};
for(int i = 0; i < (1 << m); ++i){
ll wei = 0, val = 0;
for(int j = 0; j < m; ++j){
if(i & (1 << j)){
wei += b[j];
val += c[j];
}
}
if(wei <= w){
ans = max(ans, add(w - wei) + val);
}
}
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0