結果

問題 No.1071 ベホマラー
コンテスト
ユーザー tsuishi
提出日時 2021-04-13 12:19:05
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 35 ms / 2,000 ms
コード長 4,848 bytes
コンパイル時間 1,148 ms
コンパイル使用メモリ 33,664 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-29 13:15:09
合計ジャッジ時間 2,609 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <math.h>
// №1071 ベホマラー
// ***********************
// 実装すると間に合わない。
// 回数のメモだけして、一切シミュレートしない
// 1.最初に損益分岐点の人数までベホマラーして人数を減らす
// 2.残りはホイミ
// for debug
#define DEBUGf

#define NOP do{}while(0)
#ifdef DEBUG
#define TRACE(...) do{printf(__VA_ARGS__);fflush(stdout);}while(0)
#define TRACECR do{printf("\n");fflush(stdout);}while(0)
#else
#define TRACE(...) NOP
#define TRACECR NOP
#endif

#define PRINCR printf("\n")
#define NOCR(strig) do{char *p;p=strchr(strig,'\n');if(p)*p='\0';}while(0)
// The out-of-date function
#define	asctime(...)	asctime_s(...)
#define	atof(a)		strtod(a,'\0')
#define	atoi(a)		((int)strtol(a,'\0'))
#define	atol(a)		strtol(a,'\0')
#define	ctime(...)		ctime_s(...)
#define	strlen(a)	mystr_len(a)
//#define	fopen(...)		fopen_s(...)
//#define	freopen(...)	freopen_s(...)
//#define	rewind(a)		fseek(a,0L,SEEK_SET)
//#define	setbuf(a,b)		setvbuf(a,b,_IOFBF,BUFSIZ)

// for stdio
#define INPUT(str) do{char *p;fgets(str,sizeof(str),stdin);p=strchr(str,'\n');if(p)*p='\0';}while(0)
#define mygc(c) (c)=getchar()
static char *getinput( char* str );
static void read1(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
static void read2(int *x, int *y){read1(x);read1(y);}
static char *getinput(char* str) {char c;char *cp;cp=&str[0];c=fgetc(stdin);while( c != EOF ){if((c==' ')||( c=='\n')) break;*cp++=c;c=fgetc(stdin);}*cp='\0';return &str[0];}
static int max(int a,int b){if(a>b){return a;}return b;}
static int min(int a,int b){if(a<b){return a;}return b;}
// for readaility
typedef	long long	lolong;
const int	INF = 1e9;
const int	MOD = 1e9+7;
const lolong	LINF = 1e18;
#define PI	  ((double)3.141592653589793238462643383279)
#define	YES(a)	printf("%s",((a)?"YES":"NO"))
#define	Yes(a)	printf("%s",((a)?"Yes":"No"))
#define OK(a)	printf("%s",((a)?"OK":"NG"))
#define Ok(a)	printf("%s",((a)?"Ok":"Ng"))
#define	POSSIBLE(a)		printf("%s",((a)?"POSSIBLE":"IMPOSSIBLE"))
#define	Possible(a)		printf("%s",((a)?"Possible":"Impossible"))
#define SWAP(type,a,b) do{type _c;_c=a;a=b;b=_c;}while(0)
#define REP(a,b) for(int a=0;a<(int)(b);++a)
#define REP1(a,b) for(int a=1;a<=(b);++a)
#define FLOOP(a,b) for(a=0;a<(b);++a)
#define FLOOP1(a,b) for(a=1;a<=(b);++a)
#define	ABS(c)	 ((c)<0?(-(c)):(c))
#define LSB(i) ((i) & -(i))

#define INPBUF (30+3)
#define	data_s	int
// ***********************
// ***********************
static int cmpint123(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
static int cmpint321(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
static int cmpcharABC(const void *a,const void *b){if(*(char *)a>*(char *)b){return 1;}if(*(char *)a==*(char *)b){return 0;}return -1;}
static int cmpcharVBA(const void *a,const void *b){if(*(char *)a<*(char *)b){return 1;}if(*(char *)a==*(char *)b){return 0;}return -1;}
static int mystr_len(char *str){int i=0;do{if(str[i]=='\0')break;i++;if(i>9999)break;}while(1);return i;}
// ***********************
// https://yukicoder.me/problems/no/885
// ***********************
// ***********************
// ***********************
// ***********************
// ***********************
// 外部変数
// ***********************
int main() {
	char	str[10*5+3];
	int		human;
	int		heal;
	long		hoimi,behomalar;
	long	val;
	int		nokori;
	long	used = 0L;
	int		*nlp;
	int		bep;

    INPUT( str );
	sscanf( str,"%d %d %ld %ld", &human , &heal, &hoimi, &behomalar );
	nlp = malloc( sizeof( int ) * human );
	REP(i,human) {
        getinput( str );
		sscanf( str ,"%d", &val );
		nlp[i] = ceil(((double)val - 1.) / (double)heal) ;	// 全快に必要な回数
	}
	bep = behomalar / hoimi;	// ホイミよりベホマラーした方が良い人数

	qsort( nlp, human , sizeof(nlp[0]), cmpint321 );
	nokori = human;

	if( bep < human && nlp[bep]) {
		// ホイミが有効な人数まで強制的に減らす
		if( nokori > bep ) {
			// 順位が損益分岐の人を全快させる
			REP(i,bep)  nlp[i]-=nlp[bep];	// ついでに最大HPが多い人も回復、最大HPが少ない人は全快確定してるので放置
			used = behomalar * nlp[bep];	// 全快に必要なMPを計算
		}
		nokori = 0;REP(i,bep) if( nlp[i] > 0 ) nokori++;	// 棚ぼた全快した人がいるかもしれないので人数を数え直す
	}
	val = 0; REP(i, nokori ) val += nlp[i];	// 残りホイミ必要回数
	used += hoimi * val;	// 高速化のために掛け算はループ外で

	printf("%ld\n", used );
	free( nlp );
}
0