/* * @author Jan 'Toman' Tomanek */ #include #include #include using namespace std; vector soucty; size_t N; long long S; // -------------------------------------------------------------------------------- // struct Podposloupnost { /* Konstruktor nastavi Zacatek a Konec podposloupnosti na index 0. Konstruktor muzeme volitelne volat s parametrem _Soucet, ktery nastavi Soucet podposloupnosti na danou hodnotu. Defaultne je nastavena na 0. */ Podposloupnost(size_t Zacatek, size_t Konec): Zacatek(Zacatek), Konec(Konec) { } long long Soucet() const { return soucty[Konec + 1] - soucty[Zacatek]; } /* Vrati true, pokud je Soucet volajici instance blize k _S nez instance _Druha. Jinak vraci false.*/ bool JeLepsi(const Podposloupnost & Druha) const { return abs(Soucet() - S) < abs(Druha.Soucet() - S); } bool JePlatny() const { return Zacatek <= Konec && Konec < N; } /* Provede vypis na standardni vystup ve tvaru. Vypis obsahuje poprade tri cisla - Index zacatku podposloupnosti - Index konce podposloupnosti - Soucet prvku podposloupnosti Indexy jsou interne cislovany od 0, pri vypisu jsou ale o 1 zvetseny. */ void Print() const { printf("%lu %lu %lld\n", Zacatek, Konec, Soucet()); } /* Zacatek a Konec jsou indexy zacatku a konce podposloupnosti v ramci zadane * posloupnosti. */ size_t Zacatek, Konec; }; // -------------------------------------------------------------------------------- // int main() { /* nacteme N a S */ if(scanf("%lu %lld", &N, &S) != 2) return 1; /* Nacteme posloupnost */ vector posloupnost (N); for(auto & noveCislo: posloupnost) { if(scanf("%lld", &noveCislo) != 1) return 1; } /* Spocitame prefixove soucty */ soucty.resize(N + 1); soucty[0] = 0; for (size_t i = 0; i < N; i++) { soucty[i + 1] = soucty[i] + posloupnost[i]; } /* Vytvorime pomocne struktury pro reseni : * 'aktualni' je podposloupnost, kterou prave zkoumame, * 'nejlepsi' je dosud nejlepsi nalezena podposloupnost * Na zacatku podposloupnost obsahuje pouze prvni prvek posloupnosti. * Inicializujeme proto Soucet podposloupnosti na tuto hodnotu. */ Podposloupnost nejlepsi (0, 0); Podposloupnost aktualni (0, 0); for (aktualni.Zacatek = 0; aktualni.Zacatek < N; aktualni.Zacatek++) { /* Binárně vyhledáme úsek [Zacatek, Konec] tak, aby měl co nejmenší součet větší než S */ auto konec = lower_bound(soucty.begin(), soucty.end(), S + soucty[aktualni.Zacatek]); /* Pokud jsme nalezli něco rozumného, vyzkoušíme tento úsek */ aktualni.Konec = konec - soucty.begin() - 1; if (aktualni.JePlatny()) { if (aktualni.JeLepsi(nejlepsi)) nejlepsi = aktualni; } /* Pokud existuje, vyzkoušíme ještě součet menší než S */ aktualni.Konec--; if (aktualni.JePlatny()) { if (aktualni.JeLepsi(nejlepsi)) nejlepsi = aktualni; } } /* Nakonec jen vypiseme vysledek.*/ nejlepsi.Print(); return 0; }