codeforces 417AElimination

codeforces 417AElimination

​​ The finalists of the “Russian Code Cup” competition in 2214 will be the participants who win in one of the elimination rounds.

The elimination rounds are divided into main and additional. Each of the main elimination rounds consists of c problems, the winners of the round are the first n people in the rating list. Each of the additional elimination rounds consists of d problems. The winner of the additional round is one person. Besides, k winners of the past finals are invited to the finals without elimination.

As a result of all elimination rounds at least n·m people should go to the finals. You need to organize elimination rounds in such a way, that at least n·m people go to the finals, and the total amount of used problems in all rounds is as small as possible.

Input The first line contains two integers c and d (1 ≤ c, d ≤ 100) — the number of problems in the main and additional rounds, correspondingly. The second line contains two integers n and m (1 ≤ n, m ≤ 100). Finally, the third line contains an integer k (1 ≤ k ≤ 100) — the number of the pre-chosen winners.

Output In the first line, print a single integer — the minimum number of problems the jury needs to prepare.

Examples Input 1 10 7 2 1 Output 2 Input 2 2 2 1 2 Output 0 题意：给定两种比赛 一种比赛需要c题但是可以有n个获胜者 另一种比赛是d题 只可以有一个获胜者那么 我需要求我确定N*m个获胜者最少需要多少试题 注意还有往届获胜的k个选手可以直接参赛

#include#include#include#define N 11000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}int c,d,n,m,k,f[N];int main(){ //freopen("cf.in","r",stdin); c=read();d=read();n=read();m=read();k=read(); if (n*m<=k){puts("0");return 0;}memset(f,0x3f,sizeof(f));f[0]=0; for (int i=1;i<=n*m;++i){ if (i>=n) f[i]=f[i-n]+c; f[i]=min(f[i],f[i-1]+d); }int ans=0x3f3f3f3f; for(int i=n*m-k;i<=n*m;++i) ans=min(ans,f[i]); printf("%d",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。