Mozzarelle di bufala

Salerno è la patria delle mozzarelle di bufala.
A Monica e Paola sono state regalate N mozzarelle di bufala, tutte di tipologie diverse.
Monica e Paola, dopo aver trascorso vari giorni a Salerno, hanno provato tutti i tipi di mozzarelle e hanno entrambe ormai sviluppato delle preferenze.
Il vostro compito è quello di aiutare Monica e Paola a dividersi le mozzarelle.

In particolare, sia Monica che Paola hanno dato un voto, espresso da un numero intero maggiore o uguale a 0, ad ogni mozzarella.
I voti, ovviamente, non sono necessariamente correlati.
Dovete dividere le N mozzarelle (N è un intero positivo pari) in due gruppi di N/2 mozzarelle, uno per Monica e l’altro per Paola, in maniera che la somma complessiva dei voti (cioè, la somma dei voti di Monica relativa al gruppo di mozzarelle per Monica sommata alla somma dei voti di Paola relativa al gruppo di mozzarelle per Paola) sia massima.

Per esempio, supponiamo che ci siano le seguenti 8 mozzarelle, con i seguenti voti:

In questo caso la soluzione migliore consiste nel dividere le mozzarelle nei due gruppi (1, 3, 4, 6) per Monica, e (2, 5, 7, 8) per Paola.
In questo modo la somma totale è 48, ottenuta sommando 27 (dalle mozzarelle di Monica) con 21 (dalle mozzarelle di Paola).
Non è possibile trovare una divisione delle mozzarelle che totalizzi un valore migliore.

Scarica il testo originale in PDF.

Esempi di input/output

Ottiene il 92% del punteggio (troppo spazio, troppo tempo…)

#include
#include
#include
#include
using namespace std;

#define MAXN 10000000

long long N, i;

struct       VOTO { int m, p; };
vector voti;

bool cmp(VOTO a, VOTO b)
{
	int diff1=a.m-a.p;
	int diff2=b.m-b.p;
	
    if(diff1 > diff2) return true;
	else              return false;	                        
}

int main()
{		
    ifstream fin ( "input.txt");
    ofstream fout("output.txt");
    
    VOTO voto;
    fin >> N;
    for(i=0; i> voto.m >> voto.p;
	    voti.push_back(voto);
    }
	sort(voti.begin(), voti.end(), cmp);

	long long totale=0;
	
	for(i=0  ; i < N/2; i++) totale += voti[i].m;
	for(i=N/2; i < N  ; i++) totale += voti[i].p;
    
	fout << totale;
    return 0;
}