Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на С++:

#include < iostream >
using namespace std;
#define MID 401

struct xy_pair{
	int x;
	int y;
};

xy_pair seq[201];

int opt[24][810][24]={0};

int main()
{
	int i,j,k,l,tmp,p;
	int max=MID,min=MID;
	int nmax=MID,nmin=MID;
	int tmp_x,tmp_y;
	int m,n;
	for(l=1;;++l){
          opt[0][MID][23]=l;
          opt[0][MID][22]=0;
          cin>>n>>m;
          if (0==n) break;
          max=MID;
          min=MID;
          nmax=MID;
          nmin=MID;
          for(i=0;i<n;++i){
  	    cin>>tmp_x>>tmp_y;
	    seq[i].x=tmp_x-tmp_y;
	    seq[i].y=tmp_x+tmp_y;
	    for (j=m-1;j>=0;--j) {
              for (k=min;k<=max;++k) {
	        if (l==opt[j][k][23]) {
                  tmp=k+seq[i].x;
                  if ((opt[j][k][22]+seq[i].y)>opt[j+1][tmp][22] 
	            || opt[j+1][tmp][23]!=l){
	               opt[j+1][tmp][23]=l;
	               opt[j+1][tmp][22]=opt[j][k][22]+seq[i].y;
	               if (tmp<nmin) nmin=tmp;
	               if (tmp>nmax) nmax=tmp;
	               for (p=0;p<j;p++) {
                          opt[j+1][tmp][p]=opt[j][k][p];
	              }
 	              opt[j+1][tmp][j]=i+1;
                  }
	       }
           }
	}
	max=nmax;
	min=nmin;
    }
    for (i=0;i<MID;++i) {
	if (opt[m][MID+i][23]==l && opt[m][MID-i][23]==l) {
           if (opt[m][MID+i][22]>=opt[m][MID-i][22]) {
	      cout<<"Jury #"<<l<<endl<<"Best jury has value "<<(opt[m][MID+i][22]+i)/2
	        <<" for prosecution and value "<<(opt[m][MID+i][22]-i)/2<<" for defence:\n";
	      for (j=0;j<m;++j) {
                 cout << ' ' <<opt[m][MID+i][j];
	      }
	      cout<<endl<<endl;
           }
           else if(opt[m][MID+i][22]<opt[m][MID-i][22]){
	     cout<<"Jury #"<<l<<endl<<"Best jury has value "<<(opt[m][MID-i][22]-i)/2
	        <<" for prosecution and value "<<(opt[m][MID-i][22]+i)/2<<" for defence:\n";
	     for (j=0;j<m;++j) {
               cout << ' ' <<opt[m][MID-i][j];
	    }
	 cout<<endl<<endl;
         }
         break;
      }
     else if (opt[m][MID+i][23]==l) {
        cout<<"Jury #"<<l<<endl<<"Best jury has value "<<(opt[m][MID+i][22]+i)/2
          <<" for prosecution and value "<<(opt[m][MID+i][22]-i)/2<<" for defence:\n";
        for (j=0;j<m;++j) {
	  cout << ' ' <<opt[m][MID+i][j];
        }
       cout<<endl<<endl;
       break;
    }
    else if (opt[m][MID-i][23]==l) {
      cout<<"Jury #"<<l<<endl<<"Best jury has value "<<(opt[m][MID-i][22]-i)/2
         <<" for prosecution and value "<<(opt[m][MID-i][22]+i)/2<<" for defence:\n";
      for (j=0;j<m;++j) {
	cout << ' ' <<opt[m][MID-i][j];
      }
     cout<<endl<<endl;
     break;

    }
   }
 }
 return 0;
}