#include #include #include #include #include // №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*(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 ); }