#include #include #include #include inline void fastRead_uint(int *a) { register int c=getchar_unlocked(); for(;(c<48 || c>57);c = getchar_unlocked()); *a=0; for(;c>47 && c<58;c = getchar_unlocked()) {*a=(*a<<1) + (*a<<3) + c - 48;} } inline void fastRead_int(int *a) { register int c=getchar_unlocked(); int neg=0; for(;(c<48 || c>57) && c != '-';c = getchar_unlocked()); *a=0; if(c=='-') {neg=1;c=getchar_unlocked();} for(;c>47 && c<58;c = getchar_unlocked()) {*a=(*a<<1) + (*a<<3) + c - 48;} if(neg) *a=-(*a); } int main(){ int wczytany_rozmiar_tablicy; int podtablice; fastRead_uint(&wczytany_rozmiar_tablicy); fastRead_uint(&podtablice); int rozmiar_tablicy = wczytany_rozmiar_tablicy + 1; int** tablica = new int*[rozmiar_tablicy]; int i; int i2; for(i = 0; i < rozmiar_tablicy; i++){ tablica[i] = new int[rozmiar_tablicy]; } int wczytywana; for(i = 1; i < rozmiar_tablicy; i++){ tablica[0][i] = 0; tablica[i][0] = 0; for(i2 = 1; i2 < rozmiar_tablicy; i2++){ fastRead_int(&wczytywana); tablica[i][i2] = wczytywana + tablica[i][i2-1] + tablica[i-1][i2] - tablica[i-1][i2-1]; } } int startY; int start_X; int end_Y; int end_X; long long int suma_podmacierzy; long long int suma_wszystkich_podmacierzy = 0; std::map ilosc_sum_podmacierzy; int pozycja_klasy = -1; for(i = 0; i < podtablice; i++){ fastRead_uint(&startY); fastRead_uint(&start_X); fastRead_uint(&end_Y); fastRead_uint(&end_X); suma_podmacierzy = tablica[end_Y+1][end_X+1] + tablica[startY][start_X] - tablica[startY][end_X+1] - tablica[end_Y+1][start_X]; suma_wszystkich_podmacierzy += suma_podmacierzy; ilosc_sum_podmacierzy[suma_podmacierzy] = ilosc_sum_podmacierzy[suma_podmacierzy] + 1; } long long int najwieksza_ilosc = 0, ilosc_wystapien_najwiekszej = 0; for(std::map::iterator i3 = ilosc_sum_podmacierzy.begin(); i3 != ilosc_sum_podmacierzy.end(); i3++) { if(i3->second > najwieksza_ilosc){ ilosc_wystapien_najwiekszej = 1; najwieksza_ilosc = i3->second; } else if(i3->second == najwieksza_ilosc) ilosc_wystapien_najwiekszej = ilosc_wystapien_najwiekszej + 1; } long long int srednia_wartosc = suma_wszystkich_podmacierzy / podtablice; std::cout << ilosc_sum_podmacierzy.size() << " " << ilosc_wystapien_najwiekszej << " " << srednia_wartosc; return 0; }