#include #include #include #include // getchar_unlocked or getchar #define getChar getchar_unlocked using namespace std; // http://www.algorytm.edu.pl/fast-i-o.html inline void wczytajLiczbe(int *liczba) { register char c = 0; register int znak_liczby = 1; while(c < 33) c = getChar(); if(c == 45) { znak_liczby = -1; c = getChar(); } (*liczba) = 0; while(c > 32) { (*liczba) = (*liczba) * 10ULL + (c - 48); c = getChar(); } (*liczba) *= znak_liczby; } // http://www.algorytm.org/algorytmy-sortowania/sortowanie-szybkie-quicksort/quick-1-c.html int partition(int tablica[], int p, int r) // dzielimy tablice na dwie czesci, w pierwszej wszystkie zbiorWyjsciowy_kolejkaLiczby sa mniejsze badz rowne x, w drugiej wieksze lub rowne od x { int x = tablica[p]; // obieramy x int i = p, j = r, w; // i, j - indeksy w tabeli while (true) // petla nieskonczona - wychodzimy z niej tylko przez return j { while (tablica[j] > x) // dopoki elementy sa wieksze od x j--; while (tablica[i] < x) // dopoki elementy sa mniejsze od x i++; if (i < j) // zamieniamy miejscami gdy i < j { w = tablica[i]; tablica[i] = tablica[j]; tablica[j] = w; i++; j--; } else // gdy i >= j zwracamy j jako punkt podzialu tablicy return j; } } void quicksort(int tablica[], int p, int r) // sortowanie szybkie { int q; if (p < r) { q = partition(tablica,p,r); // dzielimy tablice na dwie czesci; q oznacza punkt podzialu quicksort(tablica, p, q); // wywolujemy rekurencyjnie quicksort dla pierwszej czesci tablicy quicksort(tablica, q+1, r); // wywolujemy rekurencyjnie quicksort dla drugiej czesci tablicy } } int main() { register int n, m, k; wczytajLiczbe(&n); wczytajLiczbe(&m); wczytajLiczbe(&k); int** multizbiory = new int*[n]; int* rozmiaryMultizbiorow = new int[n]; register int rozmiarMultizbioru; int* multizbior; register int i; register int i2; register int elementMultizbioru; for(i = 0; i < n; ++i) { wczytajLiczbe(&rozmiarMultizbioru); multizbior = new int[rozmiarMultizbioru]; for(i2 = 0; i2 < rozmiarMultizbioru; ++i2) { wczytajLiczbe(&(multizbior[i2])); } quicksort(multizbior, 0, rozmiarMultizbioru - 1); rozmiaryMultizbiorow[i] = rozmiarMultizbioru; multizbiory[i] = multizbior; } register int idMultizbioru_1; register int idMultizbioru_2; priority_queue zbiorWyjsciowy_kolejkaLiczby; register int zbiorWyjsciowy_sumaElementow = 0; register int zbiorWyjsciowy_rozmiar = 0; register int zbiorWyjsciowy_maksymalnaWartosc = 2000000000; for(i = 0; i < k; ++i) { wczytajLiczbe(&idMultizbioru_1); wczytajLiczbe(&idMultizbioru_2); if(zbiorWyjsciowy_sumaElementow % 2 == 0) { multizbior = multizbiory[idMultizbioru_1]; rozmiarMultizbioru = rozmiaryMultizbiorow[idMultizbioru_1]; } else { multizbior = multizbiory[idMultizbioru_2]; rozmiarMultizbioru = rozmiaryMultizbiorow[idMultizbioru_2]; } for(i2 = 0; i2 < rozmiarMultizbioru; ++i2) { if(multizbior[i2] < zbiorWyjsciowy_maksymalnaWartosc || zbiorWyjsciowy_rozmiar < m) { ++zbiorWyjsciowy_rozmiar; zbiorWyjsciowy_sumaElementow += multizbior[i2]; zbiorWyjsciowy_kolejkaLiczby.push(multizbior[i2]); if(zbiorWyjsciowy_rozmiar > m) // usun ostatni { zbiorWyjsciowy_sumaElementow -= zbiorWyjsciowy_kolejkaLiczby.top(); zbiorWyjsciowy_kolejkaLiczby.pop(); --zbiorWyjsciowy_rozmiar; } zbiorWyjsciowy_maksymalnaWartosc = zbiorWyjsciowy_kolejkaLiczby.top(); } else { break; // nastepne sa wieksze, nie wczytywac } } } map counter; register long long int total = 0; register int tmp; while(!zbiorWyjsciowy_kolejkaLiczby.empty()) { tmp = zbiorWyjsciowy_kolejkaLiczby.top(); zbiorWyjsciowy_kolejkaLiczby.pop(); counter[tmp] = ' '; total += tmp; } cout << total << " " << counter.size(); return 0; }