結果
問題 | No.31 悪のミックスジュース |
ユーザー |
![]() |
提出日時 | 2020-09-24 22:18:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 113 ms / 5,000 ms |
コード長 | 1,875 bytes |
コンパイル時間 | 2,260 ms |
コンパイル使用メモリ | 197,564 KB |
最終ジャッジ日時 | 2025-01-14 20:07:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; using lint = long long; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++) #define REP(i, n) FOR(i,0,n) template <typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; } template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } #ifdef HITONANODE_LOCAL #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl #else #define dbg(x) #endif int main() { int N, V; cin >> N >> V; vector<lint> C(N); cin >> C; vector<lint> v2c(N + 1); REP(i, N) v2c[i + 1] = v2c[i] + C[i]; vector<lint> dp(N * 2 + 3, 1e18); dp[0] = 0; FOR(i, 1, dp.size()) { if (i < int(v2c.size())) { chmin(dp[i], v2c[i]); } REP(j, i) { chmin(dp[i], dp[j] + dp[i - j]); } } dbg(dp); auto solve = [&](auto &&solve, lint v) -> vector<lint> { vector<lint> ret(N, 1e18); if (v + N < dp.size()) { fill(ret.begin(), ret.end(), 0); REP(i, N) if (v + i >= 0) ret[i] = dp[v + i]; } else { int head = (v - N) / 2; vector<lint> half = solve(solve, head); REP(i, half.size()) REP(j, half.size()) { REP(l, dp.size()) { lint k = head * 2 + i + j + l - v; if (k >= 0 and k < int(ret.size())) chmin(ret[k], half[i] + half[j] + dp[l]); } } } return ret; }; cout << v2c[N] + solve(solve, V - N)[0] << '\n'; }