/** * 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 */ #include <stdio.h> #include <stdlib.h> int main() { int n, m, i, j, temp, sum_white = 0, sum_black = 0; //declar un pointer ca si matrice in care stochez datele int **date; do { scanf("%d %d", &n, &m); } while ((n > 106) || (m > 104) || (n < 1) || (m < 0) || (n % 2 != 0)); printf("n=%d, m=%d\n",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 do{ scanf("%d %d",&date[i][0],&date[i][1]); } while (date[i][0]+date[i][1] != m); } //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; }