题目描述

挖矿游戏“黄金矿工”的玩家按 “↓”键发送绳索，进行挖矿。玩家在规定时间内进行挖矿，达到目标钱数即为过关。

将游戏界面视为直角坐标系，设玩家所在点为原点$(0, 0)$ ，所有金块都在 $x$ 轴以下，对于一个坐标 $(x, y)$ 的金块来说，我们需要花 $x^2+y^2$ 的时间得到金块。

如果对于两个金块，它们的坐标分别为 $(x_1, y_1)$ 和 $(x_2, y_2)$ ，并且满足 $y_1/x_1=y_2/x_2$（即两个金块在过原点的一条直线上），同时 $|y_1|<|y_2|$ ，那么第 $2$ 个金块必须在第一个金块挖出之后才能挖出。

现在已知 $n$ 个金块的坐标 $（x, y）$ 以及价值（钱数），以及游戏的限定时间，问最大可以获得的价值是多少。

输入

输出文件第一行两个整数 $n$ 和 $m$ ，表示物品数和时限。

接下来 $n$ 行，每行描述一个物品：三个整数，$x$ , $y$ 和 $c$ ，分别表示这个物品的 $x$ 、$y$ 坐标以及价值。

输出

一行一个数，表示表示最大收益。

Input

3 16
1 -1 -2
2 -2 8
-2 -2 3

Output

6

我的错误代码（输出11）

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int x,y,c;
}a[109];
int n,m,dp[10009];
bool cmp(Node a,Node b){
    if (a.x*b.y!=b.x*a.y) return a.x*b.y>b.x*a.y;
    return a.c>b.c;
}//先按斜率从小到大排序，再按价值排序
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+n+1,cmp);
    for (int i=1,k,cost,val;i<=n;i=k){//cost为花费的时间，val为能得到的价值
        for (int j=m;j>=0;j--){
            for (k=i,cost=0,val=0;k<=n;k++){
					   cost+=a[k].x*a[k].x+a[k].y*a[k].y;
                val+=a[k].c;//加入总时间与总价值
                if (j>=cost) dp[j]=max(dp[j],dp[j-cost]+val);//若所剩时间仍能将金块挖出，则将当前价值加入背包
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}