POJ1015 Jury Compromise

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
int dp[25][805],path[25][805];
int n,m;
int d[205],p[205],s[205],v[205];
bool select(int j,int k,int i)
{
    while(j>0&&path[j][k]!=i)
    {
        k-=v[path[j][k]];
        --j;
    }
    if(j>0)return 0;
    else return 1;
}
int main()
{
    int cas=0;
    while(~scanf("%d%d",&n,&m),n&&m)
    {
        memset(dp,-1,sizeof(dp));
        memset(path,0,sizeof(path));
        for(int i=1; i<=n; ++i)
            scanf("%d%d",&p[i],&d[i]),s[i]=p[i]+d[i],v[i]=p[i]-d[i];
        int fix=m*20;
        dp[0][fix]=0;
        for(int j=1; j<=m; j++)
        {
            for(int k=0; k<=2*fix; k++)
            {
                if(dp[j-1][k]>=0)
                {
                    for(int i=1; i<=n; i++)
                        if(dp[j][k+v[i]]<dp[j-1][k]+s[i])
                        {
                            if(select(j-1,k,i))
                            {
                                dp[j][k+v[i]]=dp[j-1][k]+s[i];
                                path[j][k+v[i]]=i;
                            }
                        }
                }
            }
        }
        int ans;
        for(int k=0;k<=fix;k++)
            if(dp[m][fix-k]>=0||dp[m][fix+k]>=0)
             {
                 ans=k;
                 break;
             }
        if(dp[m][fix-ans]>=dp[m][fix+ans])ans=fix-ans;
        else ans=fix+ans;
        printf("Jury #%d
",++cas);
        int c=m,psum=0,dsum=0;
        int res[m+1],cnt=-1;
        while(c>0)
        {
           res[++cnt]=path[c][ans];
           psum+=p[path[c][ans]];
           dsum+=d[path[c][ans]];
           ans-=v[path[c][ans]];
           --c;
        }
        printf("Best jury has value %d for prosecution and value %d for defence:
",psum,dsum);
        sort(res,res+cnt+1);
        for(int i=0;i<=cnt;++i)
         printf(" %d",res[i]);
        printf("

");
    }
    return 0;
}