记录编号	186124	评测结果	AAAAAAAAAA
题目名称	多人背包	最终得分	100
用户昵称	God_is_dead	是否通过	通过
代码语言	C++	运行时间	0.812 s
提交时间	2015-09-11 16:54:56	内存使用	1.29 MiB

#include<iostream>
#include <fstream>
using namespace std;

ifstream fin("bags.in");
ofstream fout("bags.out");

int f[5001][51],k,v,n,w[201],e[201];


void jia(int a[],int b[],int p){
     int i,j;
     for(i=1;i<=k;i++) if(b[i]>=0) b[i]+=p;
     int c[51],s=1;
     i=1;j=1;
     while(s<=k)
     if(a[i]>b[j]) c[s++]=a[i++];
     else c[s++]=b[j++];
     for(i=1;i<=k;i++)
     a[i]=c[i];
     for(i=1;i<=k;i++)
     if(b[i]>=p) b[i]-=p;
     
     }

int main()
{
    int i,j;
    fin>>k>>v>>n;
    for(i=1;i<=n;i++)
    fin>>w[i]>>e[i];
    
    for(j=v;j>=0;j--)
    for(i=1;i<=k;i++)
    f[j][i]=-1;
    
    f[0][1]=0;
    
    for(i=1;i<=n;i++)
    for(j=v;j>=w[i];j--)
    jia(f[j],f[j-w[i]],e[i]);
    
    int ans=0;
    for(i=1;i<=k;i++)
    ans+=f[v][i];
    fout<<ans<<endl;
    return 0;
    
    }