#145 (C++11) No.31 悪のミックスジュース

• 問題: No.31 悪のミックスジュース
• ユーザー: 184
• 提出日時: 2014-10-02 19:27:54
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,442 bytes
• コンパイル時間: 624 ms
• コンパイル使用メモリ: 73,328 KB
• 実行使用メモリ: 4,508 KB
• 最終ジャッジ日時: 2023-08-28 20:03:31
• 合計ジャッジ時間: 1,319 ms
• ジャッジサーバーID （参考情報）: judge11 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	1 ms; 4,376 KB
testcase_07	AC	1 ms; 4,380 KB
testcase_08	AC	1 ms; 4,376 KB
testcase_09	WA	-
testcase_10	AC	1 ms; 4,376 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-

ソースコード

#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <queue>

using namespace std;

/*
正解してたら匿名でも問題投稿ができる(実現度さらにアップ)！！！

%I64dが通らない、

*/

int cst[101];

int idx[101];
struct smallercost{
	bool operator()(const int &a, const int &b){
		if(cst[a]!=cst[b])return cst[a]<cst[b];
		return a<b;
	}
};
int main(){
	
	int n,v;scanf("%d%d",&n,&v);
	for(int i=0;i<n;i++)scanf("%d",&cst[i]),idx[i]=i;
	sort(idx,idx+n,smallercost());	
	
	long long sc=0;
	for(int i=0;i<n;i++)sc+=cst[i];
	vector<int> sm;
	for(int i=1;i<n;i++)if(cst[0]>=cst[i])sm.push_back(i);	
	long long csts[101]={cst[0]};

	int minidx=0;
	for(int i=1;i<n;i++)csts[i]=cst[i]+csts[i-1];
	double mincst=1000000001,dcsts[101];
	for(int i=0;i<n;i++){
		dcsts[i]=(double)csts[i]/(i+1);	
		if(mincst>dcsts[i])mincst=dcsts[i],minidx=i;
	}
	/*int uid=0;
	while(uid+1<n&&cst[0]*(uid+1)>csts[uid+1])uid++;
	*/	
	v-=n;
	if(v<=0){
		printf("%lld\n",sc);return 0;
	}
	else if(idx[0]==0){
		printf("%lld\n",v*cst[0]+sc);return 0;
	}	
	long long minc=v*csts[0],mcs;
	long long ans;
	
	for(int i=1;i<n;i++){
		if(dcsts[i]<dcsts[0]){
			mcs=v/(i+1)*csts[i];
			if(v%(i+1))mcs+=csts[v%(i+1)-1];
			if(minc>mcs)minc=mcs;
			//printf("%d\n",(int)mcs);
		}
	}
	printf("%lld",minc+sc);
	return 0;
}