1 #include 
     
       2 #define _for(i,a,b) for(int i = (a);i < b;i ++) 3 typedef long long ll; 4 using namespace std; 5 inline ll read() 6 { 7     ll ans = 0; 8     char ch = getchar(), last = ' '; 9     while(!isdigit(ch)) last = ch, ch = getchar();10     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();11     if(last == '-') ans = -ans;12     return ans;13 }14 inline void write(ll x)15 {16     if(x < 0) x = -x, putchar('-');17     if(x >= 10) write(x / 10);18     putchar(x % 10 + '0');19 }20 int N,m;21 int rs[3][60];22 struct g23 {24     int n;25     int pre;26     int c[5];27     int v[5];28 };29 g rl[65];30 int search(int t)31 {32     _for(i,0,65)33         if(rl[i].pre==t)34             return i;35     return -1;36 }37 38 int rlend = 0;39 int rnt = 0;40 int dp[100003];41 int main()42 {43     memset(dp,0,sizeof(dp));44     N = read(),m = read();45     _for(i,0,m)46         _for(j,0,3)47             rs[j][i] = read();48     49     _for(i,0,m)50         if(rs[2][i]==0)51         {52             g tmp;53             tmp.pre = i+1;54             tmp.n = 1;55             tmp.c[0] = rs[0][i];56             tmp.v[0] = rs[1][i]*rs[0][i];57             rl[rlend++] = tmp;58         }59         else60         {61             int binx = search(rs[2][i]);62             if(rl[binx].n==1)63             {64                 rl[binx].n = 2;65                 rl[binx].c[1] = rs[0][i]+rl[binx].c[0];66                 rl[binx].v[1] = rs[1][i]*rs[0][i]+rl[binx].v[0];67             }68             else if(rl[binx].n==2)69             {70                 rl[binx].n = 4;71                 rl[binx].c[2] = rs[0][i]+rl[binx].c[0];72                 rl[binx].v[2] = rs[1][i]*rs[0][i]+rl[binx].v[0];73                 rl[binx].c[3] = rs[0][i]+rl[binx].c[1];74                 rl[binx].v[3] = rs[1][i]*rs[0][i]+rl[binx].v[1];75             }76         }77         78 79     _for(i,0,rlend)80         for(int j = N+1;j >= 0;j --)81         {82             _for(k,0,rl[i].n)83                 if(j>=rl[i].c[k])84                     dp[j] = max(dp[j],dp[j-rl[i].c[k]]+rl[i].v[k]);85         }86     87     _for(i,0,100003)88         rnt = max(rnt,dp[i]);89     write(rnt);90     return 0;91 }
     

数据量不止一万