#include <iostream> #include <vector> using namespace std; typedef long long ull; // kazdy ar ma swoja aktualna dlugosc trawy i szybkosc wzrostu struct ar { ull dlugosc; ull szybkosc; }; // kazde koszenie ma swoja date dzienna oraz dlugosc, do ktorej przycieto trawe struct koszenie { ull dzien; ull dlugosc; }; ull liczba_arow, liczba_koszen, laczna_szybkosc; // pole to zbior arow (posortuje je wedlug szybkosci rosniecia trawy) vector<ar> pole; // zbior kolejnych vector<koszenie> koszenia; void sort(ull left, ull right) { // quicksort ull i = left; ull j = right; ull x = pole[left].szybkosc; do { while (pole[i].szybkosc < x) i++; while (pole[j].szybkosc > x) j--; if (i <= j) { ar temp = pole[i]; pole[i] = pole[j]; pole[j] = temp; i++; j--; } } while (i <= j); if (left < j) sort(left, j); if (right > i) sort(i, right); } void init() { cin >> liczba_arow; cin >> liczba_koszen; pole.resize(liczba_arow); koszenia.resize(liczba_koszen); laczna_szybkosc = 0; for (ull i = 0; i < liczba_arow; i++) { cin >> pole[i].szybkosc; laczna_szybkosc += pole[i].szybkosc; pole[i].dlugosc = 0; } sort(0, liczba_arow-1); for (ull i = 0; i < liczba_koszen; i++) { cin >> koszenia[i].dzien; cin >> koszenia[i].dlugosc; } } int main() { ull laczna_dlugosc = 0, niedokoszone = 0, interwal = 0, ostatni_dzien = 0, ostatnia_dlugosc = 0, niedokoszone_liczba = 0; init(); for (ull i = 0; i < liczba_koszen; i++) { interwal = koszenia[i].dzien - ostatni_dzien; // pomijam koszenie, ktora nie da zadnego plonu if (pole[liczba_arow - 1].dlugosc == 0) { pole[liczba_arow - 1].dlugosc = ostatnia_dlugosc; } if (pole[liczba_arow - 1].dlugosc + interwal * pole[liczba_arow - 1].szybkosc <= koszenia[i].dlugosc) { cout << 0 << "\n"; continue; } niedokoszone = 0; niedokoszone_liczba = 0; for (ull j = 0; j < liczba_arow; j++) { if (pole[j].dlugosc == 0) { pole[j].dlugosc = ostatnia_dlugosc; } ull nowa_dlugosc = pole[j].dlugosc + pole[j].szybkosc * interwal; if (nowa_dlugosc < koszenia[i].dlugosc) { pole[j].dlugosc = nowa_dlugosc; niedokoszone += pole[j].dlugosc; niedokoszone_liczba++; } else { pole[j].dlugosc = 0; break; } } ostatnia_dlugosc = koszenia[i].dlugosc; ostatni_dzien = koszenia[i].dzien; ull out = laczna_dlugosc + laczna_szybkosc * interwal - niedokoszone - (liczba_arow - niedokoszone_liczba) * ostatnia_dlugosc; cout << out << "\n"; laczna_dlugosc = niedokoszone + (liczba_arow - niedokoszone_liczba) * ostatnia_dlugosc; } 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 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | #include <iostream> #include <vector> using namespace std; typedef long long ull; // kazdy ar ma swoja aktualna dlugosc trawy i szybkosc wzrostu struct ar { ull dlugosc; ull szybkosc; }; // kazde koszenie ma swoja date dzienna oraz dlugosc, do ktorej przycieto trawe struct koszenie { ull dzien; ull dlugosc; }; ull liczba_arow, liczba_koszen, laczna_szybkosc; // pole to zbior arow (posortuje je wedlug szybkosci rosniecia trawy) vector<ar> pole; // zbior kolejnych vector<koszenie> koszenia; void sort(ull left, ull right) { // quicksort ull i = left; ull j = right; ull x = pole[left].szybkosc; do { while (pole[i].szybkosc < x) i++; while (pole[j].szybkosc > x) j--; if (i <= j) { ar temp = pole[i]; pole[i] = pole[j]; pole[j] = temp; i++; j--; } } while (i <= j); if (left < j) sort(left, j); if (right > i) sort(i, right); } void init() { cin >> liczba_arow; cin >> liczba_koszen; pole.resize(liczba_arow); koszenia.resize(liczba_koszen); laczna_szybkosc = 0; for (ull i = 0; i < liczba_arow; i++) { cin >> pole[i].szybkosc; laczna_szybkosc += pole[i].szybkosc; pole[i].dlugosc = 0; } sort(0, liczba_arow-1); for (ull i = 0; i < liczba_koszen; i++) { cin >> koszenia[i].dzien; cin >> koszenia[i].dlugosc; } } int main() { ull laczna_dlugosc = 0, niedokoszone = 0, interwal = 0, ostatni_dzien = 0, ostatnia_dlugosc = 0, niedokoszone_liczba = 0; init(); for (ull i = 0; i < liczba_koszen; i++) { interwal = koszenia[i].dzien - ostatni_dzien; // pomijam koszenie, ktora nie da zadnego plonu if (pole[liczba_arow - 1].dlugosc == 0) { pole[liczba_arow - 1].dlugosc = ostatnia_dlugosc; } if (pole[liczba_arow - 1].dlugosc + interwal * pole[liczba_arow - 1].szybkosc <= koszenia[i].dlugosc) { cout << 0 << "\n"; continue; } niedokoszone = 0; niedokoszone_liczba = 0; for (ull j = 0; j < liczba_arow; j++) { if (pole[j].dlugosc == 0) { pole[j].dlugosc = ostatnia_dlugosc; } ull nowa_dlugosc = pole[j].dlugosc + pole[j].szybkosc * interwal; if (nowa_dlugosc < koszenia[i].dlugosc) { pole[j].dlugosc = nowa_dlugosc; niedokoszone += pole[j].dlugosc; niedokoszone_liczba++; } else { pole[j].dlugosc = 0; break; } } ostatnia_dlugosc = koszenia[i].dlugosc; ostatni_dzien = koszenia[i].dzien; ull out = laczna_dlugosc + laczna_szybkosc * interwal - niedokoszone - (liczba_arow - niedokoszone_liczba) * ostatnia_dlugosc; cout << out << "\n"; laczna_dlugosc = niedokoszone + (liczba_arow - niedokoszone_liczba) * ostatnia_dlugosc; } return 0; } |