#include <iostream> #include <math.h> #include <fstream> #include <stdio.h> using namespace std; bool *tabkubki; int **tablica; int ind; int iloscZnalezionych = 0; long long sumaTanizny = 0; void wypisz(int i) { for (int indextablica = 0; indextablica < i; indextablica++) cout << tablica[indextablica][0] << " " << tablica[indextablica][1] << " " << tablica[indextablica][2] << endl; } void Sortuj_szybko(int lewy, int prawy) { int i, j; int *piwot; i = (lewy + prawy) / 2; piwot = tablica[i]; tablica[i] = tablica[prawy]; for (j = i = lewy; i < prawy; i++) if (tablica[i][0] < piwot[0]) { int *tab; tab = tablica[j]; tablica[j] = tablica[i]; tablica[i] = tab; j++; } tablica[prawy] = tablica[j]; tablica[j] = piwot; if (lewy < j - 1) Sortuj_szybko(lewy, j - 1); if (j + 1 < prawy) Sortuj_szybko(j + 1, prawy); } bool Sprawdz_kubek(int *kubek) { int boolNumber = 0; int indexpusty = 0; for (int x1 = kubek[1]; x1 <= kubek[2]+kubek[1]; x1++) { if (tabkubki[x1]) boolNumber++; else indexpusty = x1; } if ((kubek[2] + 1 + kubek[1] + 1) - (kubek[1] + 1) == (boolNumber + 1)) { tabkubki[indexpusty] = true; sumaTanizny += kubek[0]; iloscZnalezionych++; return true; } return false; } void Szukaj_tanizny() { for (int i=0; i < ind; i++) { if (Sprawdz_kubek(tablica[i])) break; } } int main(int argc, char *argv[]) { int iloscKubkow; scanf("%d", &iloscKubkow); tabkubki = new bool[iloscKubkow]; for (int x = 0; x < iloscKubkow; x++) tabkubki[x] = false; if (iloscKubkow%2==0) ind = iloscKubkow*((int)ceil(iloscKubkow / 2.0)) + (int)ceil(iloscKubkow / 2.0); else ind = iloscKubkow*((int)ceil(iloscKubkow / 2.0)); tablica = new int*[ind]; int indextablica = 0; for (int wiersz = 0; wiersz < iloscKubkow; wiersz++) { for (int kolumna = 0; kolumna < iloscKubkow-wiersz; kolumna++) { tablica[indextablica] = new int[3]; scanf("%d", &tablica[indextablica][0]); tablica[indextablica][1] = wiersz; tablica[indextablica][2] = kolumna; indextablica++; } } Sortuj_szybko(0, indextablica - 1); while (iloscZnalezionych != iloscKubkow) { Szukaj_tanizny(); } cout << sumaTanizny << endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 | #include <iostream> #include <math.h> #include <fstream> #include <stdio.h> using namespace std; bool *tabkubki; int **tablica; int ind; int iloscZnalezionych = 0; long long sumaTanizny = 0; void wypisz(int i) { for (int indextablica = 0; indextablica < i; indextablica++) cout << tablica[indextablica][0] << " " << tablica[indextablica][1] << " " << tablica[indextablica][2] << endl; } void Sortuj_szybko(int lewy, int prawy) { int i, j; int *piwot; i = (lewy + prawy) / 2; piwot = tablica[i]; tablica[i] = tablica[prawy]; for (j = i = lewy; i < prawy; i++) if (tablica[i][0] < piwot[0]) { int *tab; tab = tablica[j]; tablica[j] = tablica[i]; tablica[i] = tab; j++; } tablica[prawy] = tablica[j]; tablica[j] = piwot; if (lewy < j - 1) Sortuj_szybko(lewy, j - 1); if (j + 1 < prawy) Sortuj_szybko(j + 1, prawy); } bool Sprawdz_kubek(int *kubek) { int boolNumber = 0; int indexpusty = 0; for (int x1 = kubek[1]; x1 <= kubek[2]+kubek[1]; x1++) { if (tabkubki[x1]) boolNumber++; else indexpusty = x1; } if ((kubek[2] + 1 + kubek[1] + 1) - (kubek[1] + 1) == (boolNumber + 1)) { tabkubki[indexpusty] = true; sumaTanizny += kubek[0]; iloscZnalezionych++; return true; } return false; } void Szukaj_tanizny() { for (int i=0; i < ind; i++) { if (Sprawdz_kubek(tablica[i])) break; } } int main(int argc, char *argv[]) { int iloscKubkow; scanf("%d", &iloscKubkow); tabkubki = new bool[iloscKubkow]; for (int x = 0; x < iloscKubkow; x++) tabkubki[x] = false; if (iloscKubkow%2==0) ind = iloscKubkow*((int)ceil(iloscKubkow / 2.0)) + (int)ceil(iloscKubkow / 2.0); else ind = iloscKubkow*((int)ceil(iloscKubkow / 2.0)); tablica = new int*[ind]; int indextablica = 0; for (int wiersz = 0; wiersz < iloscKubkow; wiersz++) { for (int kolumna = 0; kolumna < iloscKubkow-wiersz; kolumna++) { tablica[indextablica] = new int[3]; scanf("%d", &tablica[indextablica][0]); tablica[indextablica][1] = wiersz; tablica[indextablica][2] = kolumna; indextablica++; } } Sortuj_szybko(0, indextablica - 1); while (iloscZnalezionych != iloscKubkow) { Szukaj_tanizny(); } cout << sumaTanizny << endl; return 0; } |