結果
問題 | No.2329 Nafmo、イカサマをする |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:02:39 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 237 ms / 2,000 ms |
コード長 | 2,641 bytes |
コンパイル時間 | 5,448 ms |
コンパイル使用メモリ | 332,108 KB |
実行使用メモリ | 35,632 KB |
最終ジャッジ日時 | 2024-12-27 04:16:09 |
合計ジャッジ時間 | 7,220 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/extc++.h>using namespace std;// using namespace __gnu_pbds;// #include <boost/multiprecision/cpp_int.hpp>// using Bint = boost::multiprecision::cpp_int;// #include <atcoder/all>// using namespace atcoder;// https://atcoder.github.io/ac-library/production/document_ja/typedef long long int ll;typedef long double ld;constexpr ll mod = 1e9+7;constexpr ll INF = 9'223'372'036'854'775'807/10;#define rep(i,n) for (ll i = 0; i < ll(n); ++i)#define Rep(i,a,n) for (ll i = (a); i < ll(n); ++i)#define All(a) (a).begin(),(a).end()#define Pi acos(-1)using V = vector<ll>;using P = pair<ll,ll>;vector<ll> dx = {1, 0, -1, 0, 1, 1, -1, -1};vector<ll> dy = {0, 1, 0, -1, 1, -1, 1, -1};template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }struct Edge{ll to, cost;};using Graph = vector<vector<Edge>>;struct IoSetup {IoSetup() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << setprecision(15) << fixed;}} iosetup;void print(vector<string> &v) {for (string s : v) {cout << s << '\n';}}template<typename T>void print(vector<T> &v, int w = 0) {for (int i = 0; i < (int)v.size(); i++) {cout << right << setw(w) << v[i] << " \n"[i == (int)v.size() - 1];}}template<typename T>void print(vector<vector<T>> &v, int w = 0) {for (int i = 0; i < (int)v.size(); i++) {print(v[i], w);}}template<typename T>void print(const T& arg) {cout << arg << '\n';}template<typename T, typename... Args>void print(const T& arg, const Args&... args) {cout << arg << ' ';print(args...);}int main() {ll n, m, k;cin >> n >> m >> k;vector<ll> a(n);rep(i,n) {cin >> a[i];}queue<ll> q;q.emplace(0);vector<ll> b;b.emplace_back(0);rep(i,k/2) {queue<ll> tmp = q;while (!tmp.empty()) {ll now = tmp.front();tmp.pop();q.pop();rep(j,n) {q.emplace(now+a[j]);b.emplace_back(now+a[j]);}}}queue<ll> q2;q2.emplace(0);vector<ll> c;c.emplace_back(0);rep(i,(k+1)/2) {queue<ll> tmp = q2;while (!tmp.empty()) {ll now = tmp.front();tmp.pop();q2.pop();rep(j,n) {q2.emplace(now+a[j]);c.emplace_back(now+a[j]);}}}sort(All(b));sort(All(c));ll ans = 0;rep(i,b.size()) {ll now = b[i];ll rest = m-now;auto itr = upper_bound(All(c), rest);ll idx = itr-c.begin();if (idx == 0) continue;chmax(ans, now+c[idx-1]);}print(ans);}