結果
問題 |
No.31 悪のミックスジュース
|
ユーザー |
|
提出日時 | 2020-04-08 03:56:18 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,351 bytes |
コンパイル時間 | 967 ms |
コンパイル使用メモリ | 98,832 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-16 02:16:23 |
合計ジャッジ時間 | 1,565 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream> #include <string> #include <utility> #include <algorithm> #include <map> #include <set> #include <vector> #include <cmath> #include <cstdlib> #include <queue> #include <stack> #include <iomanip> #include <fstream> #include <unordered_map> #include <unordered_set> #include <assert.h> using namespace std; #define REP(i, n) for(ll i = 0;i < n;i++) #define REPR(i, n) for(ll i = n;i >= 0;i--) #define FOR(i, m, n) for(ll i = m;i < n;i++) #define FORR(i, m, n) for(ll i = m;i >= n;i--) #define REPO(i, n) for(ll i = 1;i <= n;i++) #define ll long long #define INF (ll)1 << 60 #define MINF (-1 * INF) #define ALL(n) n.begin(),n.end() #define MOD 1000000007 #define P pair<ll, ll> ll ans = 0; vector<ll> dp(11000, INF); int main() { ll n, v; cin >> n >> v; vector<ll> s(n), r(n); REP(i, n) { cin >> s[i]; ans += s[i]; } v -= n; if (v <= 0) { cout << ans << endl; return 0; } r[0] = s[0]; REP(i, n - 1) r[i + 1] = r[i] + s[i + 1]; vector<pair<double, ll>> p(n); REP(i, n) p[i] = pair<double, ll>((double)r[i] / (i + 1), i); sort(ALL(p)); if (v > 10000) { v -= 10000; ans += r[p[0].second] * (v / (p[0].second + 1)); v %= p[0].second + 1; v += 10000; } dp[0] = 0; REP(i, n) { REP(j, v + 1) { dp[min(v, j + i + 1)] = min(dp[min(v, j + i + 1)], dp[j] + r[i]); } } cout << ans + dp[v] << endl; }