ZeptoLab Code Rush 2015 C.Om Nom and Candies暴力

C. Om Nom and Candies
Time Limit: 1 Sec  Memory Limit: 256 MB
タイトル接続
http://codeforces.com/contest/526/problem/C
Description
A sweet little monster Om Nom loves candies very much. One day he found himself in a rather tricky situation that required him to think a bit in order to enjoy candies the most. Would you succeed with the same task if you were on his place?

One day, when he came to his friend Evan, Om Nom didn't find him at home but he found two bags with candies. The first was full of blue candies and the second bag was full of red candies. Om Nom knows that each red candy weighs Wr grams and each blue candy weighs Wb grams. Eating a single red candy gives Om Nom Hr joy units and eating a single blue candy gives Om Nom Hb joy units.
Candies are the most important thing in the world, but on the other hand overeating is not good. Om Nom knows if he eats more than C grams of candies, he will get sick. Om Nom thinks that it isn't proper to leave candy leftovers, so he can only eat a whole candy. Om Nom is a great mathematician and he quickly determined how many candies of what type he should eat in order to get the maximum number of joy units. Can you repeat his achievement? You can assume that each bag contains more candies that Om Nom can eat.
Input
The single line contains five integers
C, Hr, Hb, Wr, Wb (1 ≤ C, Hr, Hb, Wr, Wb ≤ 109).
Output
Print a single integer — the maximum number of joy units that Om Nom can get.
Sample Input

10 3 5 2 3

Sample Output
16
HINT
に言及
 
2つの品物しかない多重リュックの問題
 
問題:
ああ、正解はできないから、むやみにやるしかない.
では、1000 W個のA品を順方向に列挙し、1000 W個のA品を逆方向に列挙します.
もちろんこのようにむやみにやって、私も正確性を保証しませんが、やはりAです.
 
コード:
 

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

//const int inf=0x7fffffff;   //   

const int inf=0x3f3f3f3f;

/*



int buf[10];

inline void write(int i) {

  int p = 0;if(i == 0) p++;

  else while(i) {buf[p++] = i % 10;i /= 10;}

  for(int j = p-1; j >=0; j--) putchar('0' + buf[j]);

  printf("
");

}

*/

//**************************************************************************************



inline ll read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}



int main()

{

    ll c,hr,hb,wr,wb;

    ll ans=0;

    cin>>c>>hr>>hb>>wr>>wb;

    if(wr==wb)

    {

        cout<<c/wr*max(hr,hb)<<endl;

        return 0;

    }

    if(wr<wb)

    {

        swap(wr,wb);

        swap(hr,hb);

    }

    int time=0;

    for(int i=c/wr;i>=0;i--)

    {

        time++;

        ll sum=i*hr+(c-wr*i)/wb*hb;

        ans=max(sum,ans);

        if(time>10000000)

            break;

    }

    //cout<<ans<<endl;

        swap(wr,wb);

        swap(hr,hb);

    time=0;

    for(int i=c/wr;i>=0;i--)

    {

        time++;

        ll sum=i*hr+(c-wr*i)/wb*hb;

        ans=max(sum,ans);

        if(time>10000000)

            break;

    }

    cout<<ans<<endl;

}