結果
問題 | No.31 悪のミックスジュース |
ユーザー |
![]() |
提出日時 | 2014-09-26 00:16:59 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,116 bytes |
コンパイル時間 | 1,281 ms |
コンパイル使用メモリ | 159,332 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-14 15:49:19 |
合計ジャッジ時間 | 1,975 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:52:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 52 | scanf("%d%d",&N,&V); | ~~~~~^~~~~~~~~~~~~~ main.cpp:53:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 53 | rep(i,N) scanf("%d",C+i); | ~~~~~^~~~~~~~~~
ソースコード
#include<bits/stdc++.h>using namespace std;#define REP(i,a,b) for(i=a;i<b;i++)#define rep(i,n) REP(i,0,n)#define ll long long#define ull unsigned ll#define N_MAX 100#define V_MAX 1000000000#define C_MAX 1000000000int N, V, C[1111];int VV;ll sum[111];ll solve(void){int i, j, k, opt;ll res, tmp;static ll dp[11111];VV = V - N;sum[0] = 0;rep(i,N) sum[i+1] = sum[i] + C[i];dp[0] = 0;REP(i,1,11111) dp[i] = dp[i-1] + sum[1];REP(k,2,N+1) REP(i,k,11111) dp[i] = min(dp[i], dp[i-k]+sum[k]);opt = 1;REP(i,2,N+1){if(sum[opt] * i > sum[i] * opt) opt = i;}res = 0;k = max(0, (VV-11111) / opt);res += k * sum[opt];VV -= k * opt;while(VV >= 11111) VV -= opt, res += sum[opt];res += dp[VV];res += sum[N];return res;}int main(){int i, j, k;ll res;scanf("%d%d",&N,&V);rep(i,N) scanf("%d",C+i);assert(1 <= N && N <= N_MAX);assert(1 <= V && V <= V_MAX);rep(i,N) assert(1 <= C[i] && C[i] <= C_MAX);res = solve();printf("%lld\n",res);return 0;}