#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; } int main() { register int ostatnioWczytana; wczytajLiczbe(&ostatnioWczytana); register long long int rozmiarTablicy = ostatnioWczytana; wczytajLiczbe(&ostatnioWczytana); register long long int iloscPodmacierzy = ostatnioWczytana; // macierz[wiersz][kolumna], alokacja pamieci na spis wierszy int** macierz = new int*[rozmiarTablicy+1]; register int i; for(i = 0; i <= rozmiarTablicy; ++i) { // alokacja pamieci dla kazdego wiersza macierz[i] = new int[rozmiarTablicy+1]; // w pierwszym wierszu ustawia wartosc kolumny 'i' na 0 macierz[0][i] = 0; // w wierszu 'i' ustawia wartosc pierwszej kolumny na 0 macierz[i][0] = 0; } register int i2; for(i = 1; i <= rozmiarTablicy; ++i) { // wczytuje wartosci kolumn wiersza 'i' for(i2 = 1; i2 <= rozmiarTablicy; ++i2) { wczytajLiczbe(&ostatnioWczytana); // oblicza sume elementow od pozycji 0,0 do aktualnej macierz[i][i2] = macierz[i][i2-1] + macierz[i-1][i2] - macierz[i-1][i2-1] + ostatnioWczytana; } } register long long int wierszGorny, kolumnaLewa, wierszDolny, kolumnaPrawa, sumaElementowPodmacierzy, sumaElementowWszystkichPodmacierzy = 0; map wyniki; for(i = 0; i < iloscPodmacierzy; ++i) { wczytajLiczbe(&ostatnioWczytana); wierszGorny = ostatnioWczytana; wczytajLiczbe(&ostatnioWczytana); kolumnaLewa = ostatnioWczytana; wczytajLiczbe(&ostatnioWczytana); wierszDolny = ostatnioWczytana; wczytajLiczbe(&ostatnioWczytana); kolumnaPrawa = ostatnioWczytana; sumaElementowPodmacierzy = macierz[wierszDolny+1][kolumnaPrawa+1] + macierz[wierszGorny][kolumnaLewa] - macierz[wierszGorny][kolumnaPrawa+1] - macierz[wierszDolny+1][kolumnaLewa]; sumaElementowWszystkichPodmacierzy += sumaElementowPodmacierzy; ++wyniki[sumaElementowPodmacierzy]; } register long long int aktualnaNajwiekszaIlosc = 0, iloscWystapien = 0; for (map::iterator it=wyniki.begin(); it!=wyniki.end(); ++it) { if(aktualnaNajwiekszaIlosc < it->second) { aktualnaNajwiekszaIlosc = it->second; iloscWystapien = 1; } else if(it->second == aktualnaNajwiekszaIlosc) { ++iloscWystapien; } } cout << wyniki.size() << " " << iloscWystapien << " " << (sumaElementowWszystkichPodmacierzy / iloscPodmacierzy); return 0; }