結果

問題 No.31 悪のミックスジュース
ユーザー myantamyanta
提出日時 2017-05-05 10:06:56
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,290 bytes
コンパイル時間 380 ms
コンパイル使用メモリ 44,544 KB
実行使用メモリ 4,352 KB
最終ジャッジ日時 2023-10-12 09:41:01
合計ジャッジ時間 7,664 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<vector>


using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;


void solve_r(vi& v, vi& c, int m, int idx, ll ac, ll& result)
{
	vi w;

	if(idx>=v.size())
	{
		if(m==0 && result>ac)
		{
			result=ac;
		}
		return;
	}

	w=v;
	for(int i=0;i<=m;i++)
	{
		w[idx]=v[idx]+i;
		if(w[idx]>w[idx-1]) break;

		solve_r(w, c, m-i, idx+1, ac+(ll)c[idx]*i, result);
	}
}


ll solve(vi& v, vi& c, int m)
{
	vi w;
	ll ret;

	ret=(ll)c[0]*m;
	w=v;
	for(int i=0;i<=m;i++)
	{
		w[0]=v[0]+i;
		solve_r(w, c, m-i, 1, (ll)c[0]*i, ret);
	}
	return ret;
}


int main(void)
{
	int n, v, i, m;
	vi c, w;
	vll s;
	double ave, min_ave;
	int min_idx, base_v;
	ll result;

	while(scanf("%d%d", &n, &v)==2)
	{
		s.resize(n);
		w.resize(n);
		c.resize(n);
		for(i=0;i<n;i++)
		{
			scanf("%d", &c[i]);
			w[i]=1;
			s[i]=((i>0)?s[i-1]:0)+c[i];
		}

		if(v<=n)
		{
			printf("%lld\n", s[n-1]);
			continue;
		}

		v-=n;

		min_ave=c[0];
		min_idx=0;
		for(i=1;i<n;i++)
		{
			ave=(double)s[i]/(i+1);
			if(min_ave>ave)
			{
				min_ave=ave;
				min_idx=i;
			}
		}

		base_v=v/(min_idx+1);
		m=v-base_v*(min_idx+1);
		for(i=0;i<=min_idx;i++)
		{
			w[i]+=base_v;
		}
		result=s[n-1]+s[min_idx]*base_v+solve(w, c, m);

		printf("%lld\n", result);
	}

	return 0;
}
0