結果

問題 No.31 悪のミックスジュース
ユーザー ecotteaecottea
提出日時 2023-03-01 19:57:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,417 ms / 5,000 ms
コード長 21,797 bytes
コンパイル時間 6,626 ms
コンパイル使用メモリ 299,428 KB
実行使用メモリ 406,040 KB
最終ジャッジ日時 2023-10-14 23:31:44
合計ジャッジ時間 27,187 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1,206 ms
234,724 KB
testcase_02 AC 1,264 ms
245,912 KB
testcase_03 AC 2,417 ms
405,708 KB
testcase_04 AC 2,205 ms
405,812 KB
testcase_05 AC 2,203 ms
405,756 KB
testcase_06 AC 2 ms
4,352 KB
testcase_07 AC 2,224 ms
406,040 KB
testcase_08 AC 2,193 ms
405,640 KB
testcase_09 AC 2,258 ms
405,720 KB
testcase_10 AC 1 ms
4,352 KB
testcase_11 AC 10 ms
4,824 KB
testcase_12 AC 485 ms
100,936 KB
testcase_13 AC 1 ms
4,352 KB
testcase_14 AC 1,950 ms
359,972 KB
testcase_15 AC 3 ms
4,348 KB
testcase_16 AC 29 ms
8,784 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef HIDDEN_IN_VS // 折りたたみ用

// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS

// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;

// 型名の短縮
using ll = long long; // -2^63 ～ 2^63 = 9 * 10^18（int は -2^31 ～ 2^31 = 2 * 10^9）
using pii = pair<int, int>;	using pll = pair<ll, ll>;	using pil = pair<int, ll>;	using pli = pair<ll, int>;
using vi = vector<int>;		using vvi = vector<vi>;		using vvvi = vector<vvi>;
using vl = vector<ll>;		using vvl = vector<vl>;		using vvvl = vector<vvl>;
using vb = vector<bool>;	using vvb = vector<vb>;		using vvvb = vector<vvb>;
using vc = vector<char>;	using vvc = vector<vc>;		using vvvc = vector<vvc>;
using vd = vector<double>;	using vvd = vector<vd>;		using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;

// 定数の定義
const double PI = acos(-1);
const vi DX = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
const vi DY = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004004004004004LL;
double EPS = 1e-12;

// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;

// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0; set < (1 << int(d)); ++set) // d ビット全探索（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了

// 汎用関数の定義
template <class T> inline ll pow(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）

// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }

// 手元環境（Visual Studio）
#ifdef _MSC_VER
#include "local.hpp"
// 提出用（gcc）
#else
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define gcd __gcd
#define dump(...)
#define dumpel(v)
#define dump_list(v)
#define dump_list2D(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) while (1) cout << "OLE"; }
#endif

#endif // 折りたたみ用


#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;

//using mint = modint1000000007;
using mint = modint998244353;
//using mint = modint; // mint::set_mod(m);

istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>;
#endif


//【自然数の分割の列挙（d 個以下）】O(n の分割数)（n=50 くらいまで動く）
/*
* 自然数 n を d 個以下の自然数（広義降順）に分割する方法のリストを返す．
*/
vvi integer_partitions_len(int n, int d) {
	//【具体例】
	// (n, k) = (6, 3) のとき：
	//	0 : 6
	//	1 : 5 1
	//	2 : 4 2
	//	3 : 4 1 1
	//	4 : 3 3
	//	5 : 3 2 1
	//	6 : 2 2 2

	vvi ips;
	map<int, int> ip; // ip[i] : 分割に i を何個用いたか
	int len = 0;

	// n を k 以下の数で分割する．
	function<void(int, int)> rf = [&](int n, int k) {
		// 分割しきった場合
		if (n == 0) {
			// 分割の記録
			ips.push_back(vi());
			for (auto it = ip.rbegin(); it != ip.rend(); it++) {
				rep(i, it->second) ips.rbegin()->push_back(it->first);
			}
			return;
		}

		// 分割に使える数がもうない場か，分割の大きさが d に達した場合
		if (k == 0 || len == d) return;

		// n が k 以上のときは，n を k と n-k に分割できる．
		if (n >= k) {
			ip[k]++; len++;
			rf(n - k, k);
			len--; ip[k]--;
			if (ip[k] == 0) ip.erase(k);
		}

		// これ以上 n の分割に k を使わない場合
		rf(n, k - 1);
	};
	rf(n, n);

	return ips;
}


ll naive(int n, ll v, vl c, vi* w_min = nullptr) {
	v -= n;
	if (v <= 0) return accumulate(all(c), 0LL);

	auto seqs = integer_partitions_len((int)v, n);

	ll res = INFL; vvi w_mins;

	repe(seq, seqs) {
		vi w(seq);
		w.resize(n);
		++w;

		ll cost = 0;
		rep(i, n) cost += w[i] * c[i];

		if (res > cost) w_mins = vvi{ w };
		else if (res == cost) w_mins.push_back(w);

		chmin(res, cost);
	}
	dumpel(w_mins);

	if (w_min != nullptr) *w_min = w_mins[0];

	return res;
}


// サンプルを参考に，使う量を q+1, q+1, q+1, q, q, q, q, 1, 1, 1, 1 の形に限定する．
ll WA(int n, ll v, vl c, vi* w_min = nullptr) {
	vl C(n + 1);
	rep(i, n) C[i + 1] = C[i] + c[i];

	v -= n;
	if (v <= 0) return C[n];

	ll res = INFL; int i_min = -1;

	repi(i, 1, n) {
		ll q = v / i, r = v % i;
		ll cost = C[r] * (q + 1) + (C[i] - C[r]) * q;
		if(chmin(res, cost)) i_min = i;
	}
	res += C[n];

	if (w_min != nullptr) {
		w_min->clear();
		int q = (int)v / i_min, r = (int)v % i_min;
		rep(hoge, r) w_min->push_back(q + 1 + 1);
		rep(hoge, i_min - r)  w_min->push_back(q + 1);
		rep(hoge, n - i_min)  w_min->push_back(1);
	}

	return res;
}


//【山登り法】O(?)（遅い）
/*
* 初期解 st から始めて，スコアが改善される限り近傍への移動を続け，到達した局所解を返す．
* neib(s) は解 s の近傍解のリストを返す．calc(s) は解 s のスコアを返す．
*/
template <class T>
T hill_climbing(T st, const function<vector<T>(T)>& neib, const function<ll(T)>& calc) {
	ll sc = calc(st);

	while (true) {
		ll sc_max(sc);

		repe(nst, neib(st)) {
			ll nsc = calc(nst);

			if (chmax(sc_max, nsc)) st = nst;
		}

		if (sc_max == sc) break;
		sc = sc_max;
	}

	return st;

	/* neib と calc の定義の雛形
	using T = vl;
	function<vector<T>(T)> neib = [&](T s) {
		vector<T> res;

		return res;
	};
	function<ll(T)> calc = [&](T s) {
		ll sc = 0;

		return sc;
	};
	*/
}


ll WA_TLE(int n, ll v, vl c, vi* w_min = nullptr) {
	if (v - n <= 0) return accumulate(all(c), 0LL);

	using T = vi;
	function<vector<T>(T)> neib = [&](T s) {
		vector<T> res;

		rep(i, n) repi(j, i + 1, n - 1) {
			s[i]--; s[j]++;
			if (s[i] >= 1 && s[i] >= s[i + 1] && s[j - 1] >= s[j]) {
				res.push_back(s);
			}

			s[i] += 2; s[j] -= 2;
			if (s[j] >= 1 && (i == 0 || s[i - 1] >= s[i]) && (j == n - 1 || s[j] >= s[j + 1])) {
				res.push_back(s);
			}

			s[i]--; s[j]++;
		}

		return res;
	};
	function<ll(T)> calc = [&](T s) {
		ll cost = 0;

		rep(i, n) cost += s[i] * c[i];

		return -cost;
	};

	T st(n, 1);
	st[0] = (int)v - (n - 1);
	st = hill_climbing(st, neib, calc);
	dump(st);

	if (w_min != nullptr) *w_min = st;

	return -calc(st);
}


//【整数計画問題（2 変数，1 制約）】O(√e)
/*
* 変数 x, y(>=0) についての整数計画問題
*	maximize	a x + b y
*	subject to	c x + d y <= e
*				x >= 0
*				y >= 0
* の解の目的関数値を返し，実行可能解を sx, sy に格納する．
*
* 制約：c > 0, d > 0, e >= 0
*
*（平方分割）
*/
ll integer_programming_2var_1con(ll a, ll b, ll c, ll d, ll e, ll* sx_ = nullptr, ll* sy_ = nullptr) {
	// verify : https://atcoder.jp/contests/arc139/tasks/arc139_b

	Assert(c > 0 && d > 0 && e >= 0);

	ll sx = -1, sy = -1, res = -INFL;

	// 直線 a x + b y = const を左下方向に移動させる場合
	if (a <= 0 && b <= 0) {
		// 明らかに原点で最大となる．
		sx = 0;
		sy = 0;
		res = 0;
	}
	// 直線 a x + b y = const を左上方向に移動させる場合
	else if (a <= 0 && b > 0) {
		// 明らかに y 軸上で最大となる．
		sx = 0;
		sy = e / d;
		res = b * sy;
	}
	// 直線 a x + b y = const を右下方向に移動させる場合
	else if (a > 0 && b <= 0) {
		// 明らかに x 軸上で最大となる．
		sx = e / c;
		sy = 0;
		res = a * sx;
	}
	// 以降は直線 a x + b y = const を右上方向に移動させる場合について考える．
	else {
		// a d - b c >= 0 としておく．
		bool swap_flag = false;
		if (a * d - b * c < 0) {
			swap(a, b); swap(c, d);
			swap_flag = true;
		}

		// O(e/c) の全探索を採用する場合
		if (e / c < c) {
			// x の動ける範囲は 0 <= x <= e/c なので，x を決め打ち全探索する．
			repi(x, 0, e / c) {
				ll y = (e - c * x) / d;

				if (chmax(res, a * x + b * y)) { sx = x; sy = y; };
			}
		}
		// O(c) の全探索を採用する場合
		else {
			// 最適解 (x0, y0) においては 0 <= y0 < c なので，y を決め打ち全探索する．
			//（もし y0 >= c だと (x0 + d, y0 - c) の方が目的関数値を大きくする．）
			repi(y, 0, min(c - 1, e / d)) {
				ll x = (e - d * y) / c;

				if (chmax(res, a * x + b * y)) { sx = x; sy = y; };
			}
		}

		if (swap_flag) swap(sx, sy);
	}

	if (sx_ != nullptr) *sx_ = sx;
	if (sy_ != nullptr) *sy_ = sy;
	return res;
}


ll WA2(int n, ll v, vl c, vi* w_min = nullptr) {
	vl C(n + 1);
	rep(i, n) C[i + 1] = C[i] + c[i];

	v -= n;
	if (v <= 0) return C[n];

	ll res = INFL;

	repi(i, 1, n) repi(j, i + 1, n) repi(k, j, n) {
		ll a = i * C[k] - k * C[i];
		ll b = j * C[k] - k * C[j];
		ll x, y;
		integer_programming_2var_1con(a, b, i, j, v, &x, &y);
		ll zk = v - i * x - j * y;
		dump(i, j, k, ":", a, b, x, y, zk % k);
		
		if (zk % k != 0) continue;
		ll z = zk / k;

		if (chmin(res, C[i] * x + C[j] * y + C[k] * z) && w_min != nullptr) {
			w_min->clear();
			rep(hoge, i) w_min->push_back((int)(x + y + z + 1));
			rep(hoge, j - i) w_min->push_back((int)(y + z + 1));
			rep(hoge, k - j) w_min->push_back((int)(z + 1));
			rep(hoge, n - k) w_min->push_back((int)(0 + 1));
		}
	}
	res += C[n];
	dump(*w_min);

	return res;
}


ll WA3(int n, ll v, vl c, vi* w_min = nullptr) {
	vl C(n + 1);
	rep(i, n) C[i + 1] = C[i] + c[i]; 
	
	v -= n;
	if (v <= 0) return C[n];

	vector<pair<double, int>> ri(n + 1);
	ri[0].first = (double)INFL;
	repi(i, 1, n) ri[i] = { (double)C[i] / i, i };
	dump(ri);

	vl w(n, 1);

	while (v > 0) {
		auto [r, i] = *min_element(ri.begin(), ri.begin() + min(v, (ll)n));
		ll q = v / i;
		rep(j, i) w[j] += q;
		v %= i;
	}

	ll res = 0;
	rep(i, n) res += c[i] * w[i];

	if (w_min) {
		w_min->resize(n);
		rep(i, n) (*w_min)[i] = (int)w[i];
	}

	return res;
}


//【重さ最小化ナップサック問題（価値が小）】時間 O(N V) / 空間 O(N V)
/*
* 価値 v[i] と重さ w[i] の定まった N 個の品物から，価値がちょうど V で
* 重さが最小になるよう品物を選んだときの重さを返す（不可能なら -1 を返す．）
* また可能なら各品物を何個選んだかの一例を sel に格納する．
*
*（価値を状態とした状態 DP）
*/
ll knapsack_problem_minimize_weight(const vi& v, const vl& w, int V, vi& sel) {
	int N = sz(v); // 品物の個数

	// dp[i][j] : i 番目の品物までで価値ちょうど j を実現できる最小重さ
	// v[i], w[i] は 0-indexed で dp[i] は 1-indexed なので注意．
	vvl dp(N + 1, vl(V + 1, INFL));

	// 価値 0 を実現できる最小重さは 0 である．
	repi(i, 0, N) {
		dp[i][0] = 0;
	}

	// DP で重さ最小化ナップサック問題を解く．
	repi(i, 1, N) {
		repi(j, 1, V) {
			// i 番目の品物を選ばない場合
			dp[i][j] = dp[i - 1][j];

			// i 番目の品物の価値が j を超えていれば選べない．
			if (j - v[i - 1] < 0) {
				continue;
			}

			// i 番目の品物を選ぶ方が重さを小さくできるなら更新する．
			dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);
			dp[i][j] = min(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);
		}
	}

	// 不可能なら終了．
	if (dp[N][V] == INFL) {
		return -1;
	}

	// 可能なら DP 復元を行う．
	sel = vi(N);
	int i = N;
	ll j = V;
	while (i >= 1) {
		// i 番目の品物を選んだ場合と選ばなかった場合で重さの差があれば選んだ証拠．
		if (dp[i][j] != dp[i - 1][j]) {
			// 選んでいたなら 1 個分記録し，価値を減じておく．
			sel[i - 1]++;
			j -= v[i - 1];
		}
		else {
			// 選んでいなかったなら 1 つ前の品物について調べに行く．
			i--;
		}
	}

	return dp[N][V];
}


ll TLE(int n, ll v, vl c, vi* w_min = nullptr) {
	vl C(n + 1);
	rep(i, n) C[i + 1] = C[i] + c[i];

	v -= n;
	if (v <= 0) return C[n];

	vi val(n);
	rep(i, n) val[i] = i + 1;

	vl weight(n);
	rep(i, n) weight[i] = C[i + 1];

	vi sel;
	auto res = knapsack_problem_minimize_weight(val, weight, (int)v, sel);

	if (w_min) {
		*w_min = sel;
		repir(i, n - 1, 1) (*w_min)[i - 1] += (*w_min)[i];
		++(*w_min);
	}
	res += C[n];

	return res;
}


void zikken() {
#ifdef _MSC_VER
	mt19937_64 mt;
	mt.seed((int)time(NULL));
	uniform_int_distribution<ll> rnd(0LL, 1LL << 62);

	mute_dump = true;

	rep(hoge, 10000) {
		int n = rnd(mt) % 100 + 1;
		ll v = rnd(mt) % 1000 + 1;
		vl c(n);
		rep(i, n) {
			c[i] = rnd(mt) % 100 + 1;
		}

		vi w;
		auto res_naive = TLE(n, v, c, &w);

		// 重みは 4 種類以下っぽい？ → naive() の範囲では見つからなかっただけ
		vi w_tmp(w); uniq(w_tmp);
		if (sz(w_tmp) >= 5) {
			cout << "input:" << endl;
			cout << n << " " << v << endl;
			cout << c << endl;
			cout << "results:" << endl;
			cout << res_naive << endl;
			cout << w << endl;
		}

		//if (sz(w_tmp) == 4 && (w_tmp[3] - w_tmp[2] > 1 && w_tmp[2] - w_tmp[1] > 1)) {
		//	cout << "--------------------------" << endl;
		//	cout << "input:" << endl;
		//	cout << n << " " << v << endl;
		//	cout << c << endl;
		//	cout << "results:" << endl;
		//	cout << res_naive << endl;
		//	cout << w << endl;
		//}
	}

	exit(0);
#endif
}
/*
--------------------------
input:
11 40
4331 9514 189 2714 7692 7686 7190 985 421 810 8771
results:
171194
6 5 5 5 3 3 3 3 3 3 1
--------------------------
input:
13 39
3 2 1 2 3 2 1 2 2 3 1 1 3
results:
77
6 6 6 4 2 2 2 2 2 2 2 2 1
--------------------------
input:
12 50
3 3 3 1 3 1 1 3 3 1 1 3
results:
108
7 5 5 5 5 5 5 3 3 3 3 1
--------------------------
input:
15 50
3 3 3 3 3 1 1 1 1 1 3 3 1 3 3
results:
106
6 4 4 4 4 4 4 4 4 4 2 2 2 1 1
--------------------------
input:
62 431
96 37 100 45 32 61 76 100 83 71 55 53 33 14 21 61 64 38 88 56 14 55 90 56 24 37 98 51 86 12 76 2 37 42 10 91 2 54 79 19 1 36 58 19 61 17 95 28 98 2 53 5 79 61 73 74 37 3 41 16 82 63
results:
21550
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 6 6 6 6 6 6 4 3 3 3 3 3 3 3 1 1
*/


//【重さ最小化個数制限付きナップサック問題（単価が小）】O(n^2 max(v)^2) 
/*
* 価値 v[i]，重さ w[i], 最大個数 m[i] の定まった n 個の品物から，価値がちょうど V になるよう
* 品物を選んだときの重さの最小値を返す（不可能なら INFL を返す．）
* また品物 i を何個選んだかを sel[i] に格納する．
*/
ll knapsack_problem_minimize_weight(const vi& v, const vl& w, const vl& m, ll V, vl* sel = nullptr) {
	//【方法】
	// 品物の個数を m2[i] = min(m[i], max(v)) に制限すれば，
	// 価値の和が小さい場合の重さ最小化ナップサック問題として解ける．
	// その解それぞれに対し，残る価値を単位重さについて貪欲に埋めていく．

	int n = sz(v);

	// m2[i] : 制限後の品物 i の個数
	vi m2(n);
	int v_m = *max_element(all(v));
	rep(i, n) m2[i] = (int)min(m[i], (ll)v_m);

	// 価値の和が小さい場合の重さ最小化個数制限付きナップサック問題を解く．
	int v_max = 0;
	rep(i, n) v_max += v[i] * m2[i];

	// dp[i][j] : 品物 [0..i) の中で価値 j を実現できる最小重さ
	vvl dp(n + 1, vl(v_max + 1, INFL));
	dp[0][0] = 0;

	// 配る DP（スライド最小値を用いて高速化）
	rep(i, n) {
		if (v[i] <= 0) {
			repi(j, 0, v_max) dp[i + 1][j] = dp[i][j];
			continue;
		}

		// 価値が jr (mod v[i]) のところだけを見ていく．
		rep(jr, v[i]) {
			// 現在の最小値の位置と，今後最大値になりうる数の位置を昇順に入れておくデック
			deque<int> q;

			repi(jq, 0, (v_max - jr) / v[i]) {
				int j = jq * v[i] + jr;

				// 現在の最小値が注目区間の外に出たら，デックの先頭から削除する．
				if (!q.empty() && q.front() <= j - (m2[i] + 1) * v[i]) q.pop_front();

				// 新しく区間に入る数以上の数は，今後最小値とはなりえないのでデックの末尾から削除する．
				while (!q.empty()) {
					ll dp2_j = dp[i][j] - jq * w[i];
					ll dp2_back = dp[i][q.back()] - q.back() / v[i] * w[i];
					if (dp2_j > dp2_back) break;

					q.pop_back();
				}

				// 新しく区間に入る数は，常に今後最小値となる可能性があるのでデックの末尾に追加する．
				q.push_back(j);

				// 現時点での最小値を知るには，デックの先頭が指す位置を見れば良い．
				dp[i + 1][j] = dp[i][q.front()] - q.front() / v[i] * w[i] + jq * w[i];
			}
		}
	}

	// 単位価値あたりの重さと番号の組（昇順）
	vector<pair<double, int>> weight_per_val(n);
	rep(i, n) weight_per_val[i] = { (double)w[i] / v[i], i };
	sort(all(weight_per_val));

	ll res = INFL; int j_res = -1;

	// 残る価値を単位重さについて貪欲に埋めていく．
	repi(j, 0, v_max) {
		// v1 : 残り価値
		ll v1 = V - j;
		if (v1 < 0) continue;

		ll w1 = 0;
		rep(i1, n) {
			int i = weight_per_val[i1].second;

			ll cnt = min(v1 / v[i], m[i] - m2[i]);
			w1 += cnt * w[i];
			v1 -= cnt * v[i];
		}

		// 価値ちょうど V しか許さない．
		if (v1 > 0) continue;

		if (chmin(res, dp[n][j] + w1)) j_res = j;
	}

	if (res == INFL) return INFL;

	// DP 復元を行う．
	if (sel != nullptr) {
		sel->resize(n);
		int i = n, j = j_res;
		while (i >= 1) {
			// i 番目の品物を選んだ場合と選ばなかった場合で重さの差があれば選んだ証拠．
			if (dp[i][j] != dp[i - 1][j]) {
				// 選んでいたなら 1 個分記録し，価値を減じておく．
				(*sel)[i - 1]++;
				j -= v[i - 1];
			}
			else {
				// 選んでいなかったなら 1 つ前の品物について調べに行く．
				i--;
			}
		}

		// v1 : 残り価値
		ll v1 = V - j_res;

		rep(i1, n) {
			int i = weight_per_val[i1].second;

			ll cnt = min(v1 / v[i], m[i] - m2[i]);
			(*sel)[i] += cnt;
			v1 -= cnt * v[i];
		}
	}

	return res;
}


ll solve(int n, ll v, vl c, vi* w_min = nullptr) {
	vl C(n + 1);
	rep(i, n) C[i + 1] = C[i] + c[i];

	v -= n;
	if (v <= 0) return C[n];

	vi val(n);
	rep(i, n) val[i] = i + 1;

	vl weight(n);
	rep(i, n) weight[i] = C[i + 1];

	vl m(n, INFL);

	vl sel;
	auto res = knapsack_problem_minimize_weight(val, weight, m, v, &sel);
	dump(res); dump(sel);

	if (w_min) {
		w_min->resize(n);
		rep(i, n) (*w_min)[i] = (int)sel[i];
		repir(i, n - 1, 1) (*w_min)[i - 1] += (*w_min)[i];
		++(*w_min);
	}
	res += C[n];

	return res;
}


void bug_find() {
#ifdef _MSC_VER
	// 合わない入力例を見つける．

	mt19937_64 mt;
	mt.seed((int)time(NULL));
	uniform_int_distribution<ll> rnd(0LL, 1LL << 62);

	mute_dump = true;

	rep(hoge, 10000) {
		int n = rnd(mt) % 15 + 1;
		ll v = rnd(mt) % 30 + 1;
		vl c(n);
		rep(i, n) {
			c[i] = rnd(mt) % 100 + 1;
		}

		vi w_naive, w_solve;
		auto res_naive = naive(n, v, c, &w_naive);
//		auto res_solve = WA(n, v, c, &w_solve);
		auto res_solve = solve(n, v, c, &w_solve);

		if (res_naive != res_solve) {
			cout << "----------error!----------" << endl;
			cout << "input:" << endl;
			cout << n << " " << v << endl;
			cout << c << endl;
			cout << "results:" << endl;
			cout << res_naive << endl;
			cout << w_naive << endl;
			cout << res_solve << endl;
			cout << w_solve << endl;
			cout << "--------------------------" << endl;
		}
	}

	mute_dump = false;
	exit(0);
#endif
}


int main() {
//	input_from_file("input.txt");
//	output_to_file("output.txt");
	
//	zikken();

//	bug_find();

	int n; ll v;
	cin >> n >> v;

	vl c(n);
	cin >> c;

	dump(n, v); dump(c); dump("------");

	dump(naive(n, v, c)); dump("------");

	vi w;
	auto res = solve(n, v, c, &w);
	dump(w);

	cout << res << endl;
}
0