记录编号	551794	评测结果	AAAAAAAAAA
题目名称	采药(加强版)	最终得分	100
用户昵称	ZooxTark➲	是否通过	通过
代码语言	C++	运行时间	0.960 s
提交时间	2020-06-27 13:16:35	内存使用	42.27 MiB

#include <iostream>
#include <cstdio>
#define MAXN 2500000
//#define DEBUG

using namespace std;

int w[MAXN],v[MAXN],tot = 0;
int f[MAXN],txt[21][21] = {{0},{0}};

int main()
{
#ifndef DEBUG
    freopen("crazytime.in","r",stdin);
    freopen("crazytime.out","w",stdout);
#endif // DEBUG
    int n,W;
    cin >> n >> W;
    for(int i = 0;i < n;i++)
    {
        int a,b;
        cin >> a >> b;
        txt[a][b]++;
    }
    for(int i = 1;i <= 20;i++)
    {
        for(int j = 1;j <= 20;j++)
        {
            if(!txt[i][j])
                continue;
            int t = 1,a = txt[i][j];
            while(t <= a)
            {
                w[++tot] = i*t;
                v[tot] = j*t;
                a -= t;
                t <<= 1;
            }
            if(a)
            {
                w[++tot] = i*a;
                v[tot] = j*a;
            }
        }
    }
    for(int i = 1;i <= tot;i++)
    {
        for(int j = W;j >= w[i];j--)
        {
            f[j] = max(f[j],f[j-w[i]] + v[i]);
        }
    }
    cout << f[W];
    return 0;
}