結果
問題 | No.2730 Two Types Luggage |
ユーザー |
|
提出日時 | 2024-04-21 11:50:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 609 ms / 2,000 ms |
コード長 | 8,577 bytes |
コンパイル時間 | 2,773 ms |
コンパイル使用メモリ | 220,556 KB |
最終ジャッジ日時 | 2025-02-21 08:01:02 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>#include <iostream>#include <vector>#include <math.h>#include <algorithm>#include <set>#include <map>#include <unordered_map>#include <queue>#include <deque>#include <stack>#include <string>#include <bitset>#include <iomanip>using namespace std;using ll = long long;using VVI = vector<vector<int>>;using VVL = vector<vector<ll>>;using VI = vector<int>;using VL = vector<ll>;using VS = vector<string>;using VC = vector<char>;using VP = vector<pair<int, int>>;using Graph0 = vector<vector<int>>;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define drep(i, a, b) for (int i = (int)(a);i >= (int)(b);i--)#define urep(i, a, b) for (int i = (int)(a);i <= (int)(b);i++)#define lrep(i, n) for (ll i = 0; i < (ll)(n); i++)#define ldrep(i, a, b) for (ll i = (ll)(a);i >= (ll)(b);i--)#define lurep(i, a, b) for (ll i = (ll)(a);i <= (ll)(b);i++)#define arep(i, v) for (auto i : v)#define all(a) (a).begin(), (a).end()#define yes cout << "Yes" << endl#define no cout << "No" << endl#define eyes cout << "Yes" << endl;exit(0);#define eno cout << "No" << endl;exit(0);template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b;return true;}return false;}template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b;return true;}return false;}template<typename T>void excout(T A) {cout << A << endl;exit(0);}constexpr long long INF = (1LL << 60); // INFにちゅういい!// 辺の情報struct Edge{// 行先int to;// コストint cost;};using Graph = std::vector<std::vector<Edge>>;// { distance, from }using Pair = std::pair<long long, int>;// ダイクストラ法 (1.1 基本実装)// distances は頂点数と同じサイズ, 全要素 INF で初期化しておくvoid Dijkstra(const Graph& graph, std::vector<long long>& distances, int startIndex){// 「現時点での最短距離, 頂点」の順に取り出す priority_queue// デフォルトの priority_queue は降順に取り出すため std::greater を使うstd::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> q;q.emplace((distances[startIndex] = 0), startIndex);while (!q.empty()){const long long distance = q.top().first;const int from = q.top().second;q.pop();// 最短距離でなければ処理しないif (distances[from] < distance){continue;}// 現在の頂点からの各辺についてfor (const auto& edge : graph[from]){// to までの新しい距離const long long d = (distances[from] + edge.cost);// d が現在の記録より小さければ更新if (d < distances[edge.to]){q.emplace((distances[edge.to] = d), edge.to);}}}}template<typename T>T MODS(T a, T mods) {return ((((((a + mods) % mods) + mods) % mods)));}//combination 列挙用 --int verVVI comb(int n, int r) {VVI v(n + 1, VI (n + 1, 0));for (int i = 0; i < v.size(); i++) {v[i][0] = 1;v[i][i] = 1;}for (int j = 1; j < v.size(); j++) {for (int k = 1; k < j; k++) {v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);}}return v;}vector<pair<long long, long long> > prime_factorize(long long N) {// 答えを表す可変長配列vector<pair<long long, long long> > res;// √N まで試し割っていくfor (long long p = 2; p * p <= N; ++p) {// N が p で割り切れないならばスキップif (N % p != 0) {continue;}// N の素因数 p に対する指数を求めるint e = 0;while (N % p == 0) {// 指数を 1 増やす++e;// N を p で割るN /= p;}// 答えに追加res.emplace_back(p, e);}// 素数が最後に残ることがありうるif (N != 1) {res.emplace_back(N, 1);}return res;}using UNION_TYPE = int;struct UnionFind {vector<UNION_TYPE> par, siz;UnionFind(UNION_TYPE n) : par(n, -1), siz(n, 1) {}UNION_TYPE root(UNION_TYPE x) {if (par[x] == -1) return x;else return par[x] = root(par[x]);}bool issame(UNION_TYPE x, UNION_TYPE y) {return root(x) == root(y);}bool unite(UNION_TYPE x, UNION_TYPE y) {x = root(x);y = root(y);if (x == y) return false;if (siz[x] < siz[y]) swap(x, y);par[y] = x;siz[x] += siz[y];return true;}UNION_TYPE size(UNION_TYPE x) {return siz[root(x)];}};//mod func の型に注意!!!//Union Find はUNION_TYPE で型変可能!//VI topo_sort(Graph0& G) {int N = G.size();VI IND(N, 0);rep(v, N) {arep(nv, G[v]) {IND[nv]++;}}queue<int> que;rep(v, N) {if (IND[v] == 0) {que.push(v);}}VI ANS;while (!que.empty()) {int v = que.front();ANS.push_back(v);que.pop();arep(nv, G[v]) {IND[nv]--;if (IND[nv] == 0) {que.push(nv);}}}return ANS;}void ADD(int a, int b, Graph0& G) {G[a].push_back(b);G[b].push_back(a);}VP near(int i, int j, int H, int W) {VP ans;VP cand = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}};arep(v, cand) {if (v.first < 0 or v.first >= H) continue;if (v.second < 0 or v.second >= W) continue;ans.push_back(v);}return ans;}int cast(int i, int j, int H, int W) {return ((W * i) + j);}ll pows(ll x, ll n, ll mod) {if (!n) return 1;x %= mod;ll r = pows(x, n / 2, mod);(r *= r) %= mod;if (n % 2) (r *=x) %= mod;return r;}struct COMB_MOD {ll mod;int MAX;VL fac, finv, inv;COMB_MOD(int max, ll m) {fac.assign(max, 0);finv.assign(max, 0);inv.assign(max, 0);mod = m;MAX = max;}void solve() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % mod;inv[i] = mod - inv[mod%i] * (mod / i) % mod;finv[i] = finv[i - 1] * inv[i] % mod;}}ll comb(int n, int k) {if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % mod) % mod;}};struct LCA {vector<vector<int>> parent; // parent[k][u]:= u の 2^k 先の親vector<int> dist; // root からの距離LCA(const Graph0 &G, int root = 0) { init(G, root); }// 初期化void init(const Graph0 &G, int root = 0) {int V = G.size();int K = 1;while ((1 << K) < V) K++;parent.assign(K, vector<int>(V, -1));dist.assign(V, -1);dfs(G, root, -1, 0);for (int k = 0; k + 1 < K; k++) {for (int v = 0; v < V; v++) {if (parent[k][v] < 0) {parent[k + 1][v] = -1;} else {parent[k + 1][v] = parent[k][parent[k][v]];}}}}// 根からの距離と1つ先の頂点を求めるvoid dfs(const Graph0 &G, int v, int p, int d) {parent[0][v] = p;dist[v] = d;for (auto e : G[v]) {if (e != p) dfs(G, e, v, d + 1);}}int query(int u, int v) {if (dist[u] < dist[v]) swap(u, v); // u の方が深いとするint K = parent.size();// LCA までの距離を同じにするfor (int k = 0; k < K; k++) {if ((dist[u] - dist[v]) >> k & 1) {u = parent[k][u];}}// 二分探索で LCA を求めるif (u == v) return u;for (int k = K - 1; k >= 0; k--) {if (parent[k][u] != parent[k][v]) {u = parent[k][u];v = parent[k][v];}}return parent[0][u];}int get_dist(int u, int v) { return dist[u] + dist[v] - 2 * dist[query(u, v)]; }};int main(void) {int N, M;ll W;cin >> N >> M >> W;VL A(N);VL B(M), C(M);rep(i, N) cin >> A[i];rep(i, M) cin >> B[i];rep(i, M) cin >> C[i];sort(all(A));reverse(all(A));VL S(N + 1, 0);urep(i, 1, N) S[i] = S[i - 1] + A[i - 1];ll ans = 0;rep(bit, (1 << M)) {ll w = 0;ll s = 0;rep(i, M) {if (bit & (1 << i)) {w += B[i];s += C[i];}}if (w > W) continue;ll rem = min(W - w, (ll)N);chmax(ans, s + S[rem]);}cout << ans << endl;}