/** * Denis has N boxes (N even), and each box contains M marbles which are either * black or white. He knows for each box how many black marbles it contains and * how many white marbles it contains. He now wants to split the N boxes into 2 * groups, each containing N/2 boxes, such that the sum of the black marbles in * the first group, and the white marbles in the second group is maximum. * * Input * The first line of input contains N and M, in this order. * The following N lines contain two positive integers each, denoting the number * of white marbles and the number of black marbles that are in each box. * * Output * On a single line print two integers separated by space: the number of black * marbles in the first group and the number of white marbles in the second group. * * Constraints * 1 ⤠N ⤠105 * 0 ⤠M ⤠104 * The solution is unique. * * Sample * Input Output * 4 3 5 5 * 0 3 * 3 0 * 1 2 * 2 1 * * TIME LIMIT = 3s */ #include <stdio.h> #include <stdlib.h> int main() { int n, m, i, j, temp, sum_white = 0, sum_black = 0; int **date; scanf("%d %d", &n, &m); //read input date = (int **)malloc(n*sizeof(int*)); for (i = 0; i<n; i++) { date[i] = (int *)malloc(2*sizeof(int)); //read values scanf("%d %d",&date[i][0],&date[i][1]); } //need to sort date[][] by the first column for (i = 1; i < n; i++){ for (j = 0; j < n-1; j++){ if(date[j][0] < date[j+1][0]){ temp = date[j][0]; date[j][0] = date[j+1][0]; date[j+1][0] = temp; temp = date[j][1]; date[j][1] = date[j+1][1]; date[j+1][1] = temp; } } } for (i=0;i<n;i++){ if (i>(n/2-1)){ sum_white += date[i][1]; } else { sum_black += date[i][0]; } } printf("%d %d\n",sum_black,sum_white); /* //free allocated memory for (i = 0; i<n; i++) { free(date[i]); } free(date); */ return 0; }