> The code works for the dataset I tested.

import java.io.*;
import java.util.*;

class JuryCompromise {
	static class Person {
		int prosecution, defence, sum, diff;

		Person(String line) {
			String[] tokens = line.trim().split(" ");
			prosecution = Integer.parseInt(tokens[0]);
			defence = Integer.parseInt(tokens[1]);
			sum = prosecution + defence;
			diff = prosecution - defence;
		}
	}

	static final int MAX_GRADE=20;
	static int total, select, grade_sum, grade_diff;
	static Person[] people;
	static String jury_found;

	static void findBestJury() {
		int[][] sum = new int[select][];
		String[][] list = new String[select][];
		sum[0] = new int[2*MAX_GRADE+1];
		list[0] = new String[2*MAX_GRADE+1];
		for ( int p=0; p<total; p++ ) {
			int pos = people[p].diff + MAX_GRADE;
			if ( list[0][pos]==null || sum[0][pos]<people[p].sum ) {
				sum[0][pos] = people[p].sum;
				list[0][pos] = " " + p + " ";
			}
		}
		for ( int s=1; s<select; s++ ) {
			sum[s] = new int[2*MAX_GRADE*(s+1)+1];
			list[s] = new String[2*MAX_GRADE*(s+1)+1];
			for ( int i=0; i<=2*MAX_GRADE*s; i++ ) {
				if ( list[s-1][i] == null )
					continue;
				int pre_diff = i - MAX_GRADE * s;
				for ( int p=0; p<total; p++ ) {
					if ( list[s-1][i].indexOf(" "+p+" ") >= 0 )
						continue;
					int pos = pre_diff + people[p].diff + MAX_GRADE * (s+1);
					if ( list[s][pos]==null
						|| sum[s][pos]<people[p].sum+sum[s-1][i] ) {
						sum[s][pos] = people[p].sum + sum[s-1][i];
						list[s][pos] = list[s-1][i] + p + " ";
					}
				}
			}
		}
		for ( int i=0; i<=MAX_GRADE*select; i++ ) {
			int left = -1, right = -1;
			if ( list[select-1][MAX_GRADE*select-i] != null )
				left = sum[select-1][MAX_GRADE*select-i];
			if ( list[select-1][MAX_GRADE*select+i] != null )
				right = sum[select-1][MAX_GRADE*select+i];
			if ( left==-1 && right==-1 )
				continue;
			if ( left > right ) {
				jury_found = list[select-1][MAX_GRADE*select-i];
				grade_sum = sum[select-1][MAX_GRADE*select-i];
				grade_diff = - i;
			}
			else {
				jury_found = list[select-1][MAX_GRADE*select+i];
				grade_sum = sum[select-1][MAX_GRADE*select+i];
				grade_diff = i;
			}
			break;
		}
	}

	public static void main(String[] arg) throws IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		for ( int id=1; ; id++ ) {
			String line = input.readLine().trim();
			while ( line.length() == 0 )
				line = input.readLine().trim();
			String[] tokens = line.split(" ");
			total = Integer.parseInt(tokens[0]);
			select = Integer.parseInt(tokens[1]);
			if ( total == 0 )
				break;
			people = new Person[total];
			for ( int i=0; i<total; i++ )
				people[i] = new Person(input.readLine());
			findBestJury();
			System.out.println("Jury #"+id);
			System.out.println("Best jury has value "
				+ (grade_sum+grade_diff)/2 + " for prosecution and value "
				+ (grade_sum-grade_diff)/2 + " for defence:");
			tokens = jury_found.split(" ");
			int[] value = new int[tokens.length-1];
			for ( int i=0; i<value.length; i++ )
				value[i] = Integer.parseInt(tokens[i+1]) + 1;
			Arrays.sort(value);
			for ( int i=0; i<value.length; i++ )
				System.out.print(" "+value[i]);
			System.out.println();
			System.out.println();
		}
	}
}

• Re:Always got RE... :( Can sb tell me if it is because of the input format? (3525) gongml 2005-10-12 07:22:27
• Finally, I got it... (after changing from String split func to StringTokenizer) (78) gongml 2005-10-12 07:30:10