P1064求调

P1064 求调！

代码如下

#include <bits/stdc++.h>
using namespace std;
long long money,num,cnt;
long long dui[70];
__int128 price[70][3];
__int128 impor[70][3];
__int128 gain[32010];//gain[x] = y表示x元获得的最大收益 
void enter_w(__int128 id,__int128 cost,__int128 important,__int128 q){
    if(q == 0) {
        price[id][0] = cost;
        impor[id][0] = important;
    }
    for(__int128 i = 1;i <= 2;i++){
        if(price[dui[q]][i]) continue;
        price[dui[q]][i] = cost;
        impor[dui[q]][i] = important;
        break;
    }
    return;
}

__int128 get_gain(__int128 id1,__int128 id2){
    return price[id1][id2]*impor[id1][id2];
} 
__int128 dp(){
    memset(gain,0,sizeof(gain));
    for(__int128 i = 1;i <= cnt;i++){
        __int128 y,f1,f2;
        y = get_gain(i,0);
        f1 = get_gain(i,1);
        f2 = get_gain(i,2);
        __int128 t[5],cost[5];
        t[1] = y;       cost[1] = price[i][0];
        t[2] = y+f1;    cost[2] = price[i][0]+price[i][1];
        t[3] = y+f2;    cost[3] = price[i][0]+price[i][2];
        t[4] = y+f1+f2; cost[4] = price[i][0]+price[i][1]+price[i][2];
        for(__int128 j = money;j >= 0;j--){
            for(__int128 k = 1;k <= 4;k++){
                if(j-cost[k] < 0) continue;
                gain[j] = max(gain[j],gain[j-cost[k]]+t[k]);
            }
        }
    }
    return gain[money];
}
int main(){
    scanf("%lld %lld",&money,&num);

    for(int i = 1;i <= num;i++){
        long long v,p,q;
        scanf("%lld %lld %lld",&v,&p,&q);
        if(q == 0) {cnt++;dui[i] = cnt;}
        enter_w(cnt,v,p,q);
    }

    __int128 ans = dp();
    string s = "";
    while(ans > 0){
        s = char(ans%10+'0')+s;
        ans/=10;
    }
    cout << s;
    return 0;
}