Cütlükdə (Platin)#11229
n inək düz bir sıra ilə dayanır, hər biri ya Holstein, ya da Guernsey cinsinə aiddir. i-ci inəyin cinsi b[i] ∈ {H, G} ilə verilir, i-ci inəyin mövqeyi x[i] ilə, və i-ci inəyin çəkisi y[i] ilə verilir.
Fermer Conun siqnalı ilə bəzi inəklər cütlər təşkil edir ki,
Hər bir cüt Holstein h və Guernsey g cinsli inəklərdən ibarətdir və onların mövqeləri bir-birindən ən çox k qədər uzaqdır; yəni, |x[h] − x[g]| ≤ k.
Hər bir inək ya bir cütün tərkibindədir, ya da heç bir cütə daxil deyil.
Cütlərə bölünmə maksimaldır, əgər qalan inəklərdən heç biri cüt təşkil edə bilməzsə.
Cütə daxil olmayan inəklərin mümkün çəkilərinin cəminin diapazonunu müəyyən edin, yəni
Əgər t = 1, cütə daxil olmayan inəklərin mümkün minimal çəkilərinin cəmini hesablayın.
Əgər t = 2, cütə daxil olmayan inəklərin mümkün maksimal çəkilərinin cəmini hesablayın.
Birinci sətir t, n (1 ≤ n ≤ 5000), k (1 ≤ k ≤ 10^9) ehtiva edir.
Sonra n sətir gəlir, i-ci sətir bi, x[i] (0 ≤ x[i] ≤ 10^9), y[i] (1 ≤ y[i] ≤ 10^5) ədədlərini ehtiva edir. Zəmanət verilir ki, 0 ≤ x[1] < x[2] < ... < x[n] ≤ 10^9.
Cütə daxil olmayan inəklərin minimal və ya maksimal mümkün çəkilərinin cəmini çıxarın.
İnəklər 2 və 3 cüt ola bilər, çünki onlar 1 məsafəsindədirlər, bu isə k = 4-dən kiçikdir. Bu cütləşmə maksimaldır, çünki 1 nömrəli inək yeganə qalan Guernsey cinslidir, 4 nömrəli inəkdən 5 məsafəsində və 5 nömrəli inəkdən 7 məsafəsindədir, bu isə k = 4-dən böyükdür. Cütə daxil olmayan inəklərin çəkilərinin cəmi 1 + 6 + 9 = 16.
İnəklər 1 və 2 cüt ola bilər, çünki 2 ≤ k = 4 məsafəsindədirlər, və inəklər 3 və 5 cüt ola bilər, çünki onlar 4 ≤ k = 4 məsafəsindədirlər. Bu cütləşmə maksimaldır, çünki yalnız bir inək 4 qalacaq. Çəkilərinin cəmi onun çəkisinə bərabərdir, yəni 6.
Bu nümunədə cavab 18 + 465 + 870 + 540 = 1893.
Nümunə 1
Nümunə 2
Nümunə 3