zoj 3474 Taekwondo

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int R[30],waste[30];int r[30];bool cmp(int a,int b){return R[a]-waste[a]>R[b]-waste[b];}bool wacmp(int a,int b){return waste[a]<waste[b];}bool getcmp(int a,int b){return R[a]>R[b];}main(){int T;scanf("%d",&T);while (T--){int N,S;scanf("%d%d",&N,&S);for (int i=0;i<N;i++){r[i]=i;int p[5];scanf("%d%d%d%d",&p[3],&p[2],&p[1],&R[i]);int dp[20];memset(dp,0x7f,sizeof(dp));for (int j=0;j<=10;j++)dp[0]=0;for (int j=1;j<=10;j++)for (int k=1;k<=3;k++)if (j>=k) dp[j]=min(dp[j],dp[j-k]+p[k]);waste[i]=1e9;waste[i]=min(dp[7],waste[i]);waste[i]=min(dp[8],waste[i]);waste[i]=min(dp[9],waste[i]);}int start=S;bool found=true;int K=N;sort(r,r+N,cmp);for (int i=0;i<N;i++){int j=r[i];if (R[j]-waste[j]<=0) {K=i;break;}}sort(r,r+K,wacmp);for (int i=0;i<K;i++){int j=r[i];if (start-waste[j]<=0){found=false;break;}start=start-waste[j]+R[j];}sort(r+K,r+N,getcmp);if (found)for (int z=K;z<N;z++){int j=r[z];if (start-waste[j]<=0) {found=false;break;}else start=start-waste[j]+R[j];}if (found) printf("%dn",start);else printf("non");}return 0;}