Right @ 2016-12-31 12:10:56
#include <stdio.h>
#include <string.h>
//#define max(a,b) a>b?a:b;
using namespace std;
int n,m;
int dp[800][48000];
int v[800][50],w[800][50];
int max(int a,int b)
{
if (a>b)
return a;
else
return b;
}
void csh()
{
int i,c,p,q;
scanf("%d%d",&n,&m);
n/=10;
for (i=1; i<=m; ++i)
{
scanf("%d%d%d",&c,&p,&q);
c/=10;
if (q==0)
{
w[i][0]=c;
v[i][0]=c*p;
}
else
if(w[q][1]==0) //first one
{
w[q][1]=c;
v[q][1]=c*p;
}
else //second one
{
w[q][2]=c;
v[q][2]=c*p;
}
}
}
void pack()
{
int i,j;
int a,b,c,d,e;
a=0; b=0; c=0; d=0; e=0;
for (i=1; i<=m; ++i)
{
for (j=0; j<=n; ++j)
{
e=dp[i-1][j];
if (j>=w[i][0])
a=dp[i-1][j-w[i][0]]+v[i][0];
if (j>=w[i][0]+w[i][1])
b=dp[i-1][j-(w[i][0]+w[i][1])]+v[i][0]+v[i][1];
if (j>=w[i][0]+w[i][2])
c=dp[i-1][j-(w[i][0]+w[i][2])]+v[i][0]+v[i][2];
if (j>=w[i][0]+w[i][1]+w[i][2])
d=dp[i-1][j-(w[i][0]+w[i][1]+w[i][2])]+v[i][0]+v[i][1]+v[i][2];
dp[i][j]=max(e,max(a,max(b,max(c,d))));
}
}
}
void print()
{
int i,j;
for (i=m-5; i<=m; ++i)
{
for (j=n-10; j<=n; ++j)
printf("%d ",&dp[i][j]);
printf("\n");
}
}
int main()
{
memset(dp,0,sizeof(dp));
csh();
pack();
//print();
printf("%d\n",dp[m][n]*10);
}