結果
問題 | No.2329 Nafmo、イカサマをする |
ユーザー |
|
提出日時 | 2023-05-28 15:55:01 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 4,718 bytes |
コンパイル時間 | 2,112 ms |
コンパイル使用メモリ | 142,216 KB |
実行使用メモリ | 14,252 KB |
最終ジャッジ日時 | 2024-12-27 09:39:57 |
合計ジャッジ時間 | 3,530 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
/*{{{ author: ryota2357 */#include <algorithm>#include <cassert>#include <cmath>#include <iostream>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <string>#include <tuple>#include <utility>#include <vector>namespace ryota2357{template <class T1, class T2>inline std::istream& operator>>(std::istream& is, std::pair<T1, T2>& P) noexcept {return is >> P.first >> P.second;}template <class T>inline std::istream& operator>>(std::istream& is, std::vector<T>& V) noexcept {for (auto& v : V) is >> v;return is;}template <class T>inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& V) noexcept {const auto n = V.size() - 1;for (int i = 0; i < n; ++i) os << V[i] << ' ';return os << V.back();}inline void IN(void) noexcept { return; }template <class T, class... U>inline void IN(T& t, U&... u) noexcept {std::cin >> t;IN(u...);}template <class T>inline void OUT(const T& x) noexcept { std::cout << x << '\n'; }template <class T>inline bool chmax(T& a, const T& b) noexcept { return a < b ? a = b, true : false; }template <class T>inline bool chmin(T& a, const T& b) noexcept { return a > b ? a = b, true : false; }template <class T = int>inline T read(void) {T ret = 0;char c = getchar();while ((c < '0' || '9' < c) && c != '-') c = getchar();const bool f = (c == '-') && (c = getchar());while ('0' <= c && c <= '9') {ret = 10 * ret + c - '0';c = getchar();}return f ? -ret : ret;}template <class T>inline T ceil_div(const T& a, const T& b) {assert(b != 0);return (a + (b - 1)) / b;}template <class T>inline T max(const std::vector<T>& v) { return *max_element(v.begin(), v.end()); }template <class T>inline T min(const std::vector<T>& v) { return *min_element(v.begin(), v.end()); }} // namespace ryota2357using ll = long long;using pint = std::pair<int, int>;#define rep(i, a, b) for (ll i = (a); i < ll(b); ++i)#define repr(i, a, b) for (ll i = (a); i >= ll(b); --i)#define each(x, v) for (auto& x : v)#define All(x) (x).begin(), (x).end()#define AllR(x) (x).rbegin(), (x).rend()#define Sort(x) (sort((x).begin(), (x).end()))#define SortR(x) (sort((x).rbegin(), (x).rend()))#define Unique(x) (x.erase(unique((x).begin(), (x).end()), (x).end()))#define Fill(v, n) (fill((v), (v) + sizeof(v) / sizeof(*(v)), (v)))#define INF (1073741823)#define INFL (2305843009213693951ll)using namespace std;using namespace ryota2357;/*}}}*/namespace debug{void _DEBUG_PRINT_() {static bool done = false;if (done) return;done = true;std::cout << "\033[33m[Debug Mode]\033[m" << std::endl;}void Write(void) {_DEBUG_PRINT_();std::cerr << std::endl;}template <class T, class U>void Write(const std::pair<T, U>& p) {_DEBUG_PRINT_();std::cerr << ' ' << '{' << p.first << ',' << p.second << '}' << std::endl;}template <class T>void Write(const std::set<T>& V) {_DEBUG_PRINT_();std::cerr << " {";for (const auto& v : V) std::cerr << ' ' << v;std::cerr << " }" << std::endl;}template <class T>void Write(const std::vector<T>& V, int n = -1) {_DEBUG_PRINT_();if (n < 0) n = V.size();std::cerr << " [";for (int i = 0; i < n; ++i) std::cerr << ' ' << V[i];std::cerr << " ]" << std::endl;}template <class T, class U>void Write(const std::vector<std::pair<T, U>>& V, int n = -1) {_DEBUG_PRINT_();if (n < 0) n = V.size();std::cerr << " [";for (int i = 0; i < n; ++i) std::cerr << " {" << V[i].first << ',' << V[i].second << '}';std::cerr << " ]" << std::endl;}template <class T, class... U>void Write(const T& t, const U&... u) {_DEBUG_PRINT_();std::cerr << ' ' << t;Write(u...);}} // namespace debugusing namespace debug;int n, m, k;vector<ll> a(n);set<ll> calc(int kk) {// Write("kk: ", kk);set<ll> ret;ret.insert(0);rep(_, 0, kk) {vector<ll> nw;each(prev, ret) {rep(i, 0, n) {nw.push_back(a[i] + prev);}}each(nwi, nw) {if (nwi > m) {continue;}ret.insert(nwi);}}return ret;}int main() {IN(n, m, k);a.resize(n);IN(a);auto set1 = calc(k / 2);auto set2 = calc(ceil_div(k, 2));// Write("set1: ", set1);// Write("set2: ", set2);ll ans = 0;each(e1, set1) {auto it = set2.upper_bound(m - e1);if (it == set2.begin()) {continue;}--it;chmax(ans, e1 + *it);}OUT(ans);return 0;}