結果
問題 |
No.31 悪のミックスジュース
|
ユーザー |
|
提出日時 | 2016-10-07 18:37:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,520 bytes |
コンパイル時間 | 1,737 ms |
コンパイル使用メモリ | 178,868 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-14 15:53:06 |
合計ジャッジ時間 | 2,425 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<<endl #define smax(x,y) (x)=max((x),(y)) #define smin(x,y) (x)=min((x),(y)) #define MEM(x,y) memset((x),(y),sizeof (x)) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; typedef tuple<ll, int> T; bool cmp(T a, T b){ ll ax, bx; int ay, by; tie(ax, ay) = a; tie(bx, by) = b; if(ax*by != bx*ay)return ax*by < bx*ay; else return ay < by; } ll dp[101 * 103], INF = LLONG_MAX; int main(){ int N, V; cin >> N >> V; vll C(N); rep(i, N)cin >> C[i]; vector<T> vt(N); ll sm = 0; rep(i, N){ sm += C[i]; vt[i] = mp(sm, i + 1); } sort(all(vt), cmp); V -= N; ll ans = sm; if(V >= 101*N){ int v = V - 100 * N, n; ll cost; tie(cost, n) = vt[0]; ans += v / n*cost; v %= n; V = 100 * N + v; } smax(V, 0); rep(i, 101*103)dp[i] = INF; dp[0] = 0; rep(i, N){ ll cost; int n; tie(cost, n) = vt[i]; for(int j = 0; j<V; ++j)if(dp[j]!=INF){ smin(dp[j + n], dp[j] + cost); } } ll mini = LLONG_MAX; FOR(i, V, 101 * 103)smin(mini, dp[i]); ans += mini; cout << ans << endl; }