2455 - Plaja 2

Zizi îşi va petrece concediul în această vară într-o frumoasă staţiune de la Marea Neagră. Acolo va sta N zile. Zilele

sunt numerotate de la 1 la N. În fiecare dintre cele N zile de concediu, ea intenţionează să facă plajă un număr cât

mai mare de unităţi de timp. Va trebui să ţină seama totuşi de prognoza meteo, care este nefavorabilă în K dintre cele N zile, respectiv în zilele z[1], z[2], …, z[k]. În fiecare dintre aceste K zile va ploua sau va fi prea mult soare, iar Zizi va trebui să-şi limiteze timpii de plajă la cel mult t[1], t[2], …, t[k] unităţi de timp. De asemenea, din motive de confort fizic, Zizi doreşte ca diferenţa în valoare absolută a timpilor de plajă între oricare două zile consecutive să nu depăşească T.

Cerința

Cunoscând zilele z[1], z[2], …, z[k] în care există limitările t[1], t[2], …, t[k] pentru timpul de plajă şi valoarea T, să se determine numărul maxim de unităţi de timp pe care Zizi le poate petrece la plajă într-o singură zi dintre cele N zile de concediu.

Date de intrare

Fișierul de intrare input.txt conține pe prima linie trei numere naturale N, K şi T separate printr-un spaţiu, reprezentând numărul de zile de concediu, numărul de zile în care există limitări pentru timpul de plajă şi diferenţa maximă

admisă a timpilor de plajă pentru oricare două zile consecutive. Pe fiecare dintre următoarele K linii se află câte două numere z şi t, despărțite printr-un spațiu, reprezentând numărul de ordine al unei zile cu limitări pentru timpul de plajă, respectiv limita de timp pentru ziua respectivă. Valorile z[1], z[2], …, z[k] sunt în ordine strict crescătoare.

Date de ieșire

Fișierul de ieșire output.txt va conține pe prima linie un singur număr natural tmax, reprezentând numărul maxim de

unităţi de timp pe care Zizi le poate petrece făcând plajă într-una din cele N zile de concediu.

Restricții și precizări

• 1 ≤ N ≤ 1 000 000 000
• 1 ≤ K ≤ 100 000

Exemplul 1

input.txt:

3 1 3

1 2

output.txt:

8

Explicație:

În prima zi timpul de plajă este limitat la 2 unități de timp. În ziua a doua timpul maxim de plajă este 2 + 3, iar în ziua a treia, timpul maxim este 2 + 3 + 3 = 8 unități de timp.

Exemplul 2

input.txt:

5 2 11

2 2

4 5

output.txt:

16

Explicație:

În ziua 2 timpul de plajă este limitat la 2 unități de timp, iar în zilele 1 și 3 nu există limitare. Atunci timpul maxim de plajă pentru zilele 1 sau 3 este 2 + 11 = 13. În ziua 4 timpul de plajă este limitat la 5 unități de timp, iar în ziua 5 nu există limitare. Deci în ziua 5 timpul maxim de plajă este 5 + 11 = 16.

Exemplul 3

input.txt:

99999999999999999999 2 11

2 2

4 5

Output:

Error: N is not within the valid range (1 <= N <= 1,000,000,000)

Rezolvare

# prof. Constantin Galatan
# solutie O(K * log T)

import sys

def verify_constraints(N, K):
    if not (1 <= N <= 1000000000):
        sys.exit("Error: N is not within the valid range (1 <= N <= 1,000,000,000)")
    
    if not (1 <= K <= 100000):
        sys.exit("Error: K is not within the valid range (1 <= K <= 100,000)")

def try_time(t0, i):
    return d[i + 1] - d[i] >= (t0 - t[i] + T - 1) // T + (t0 - t[i + 1] + T - 1) // T

input_file = open("input.txt", "r")
output_file = open("output.txt", "w")

N, K, T = map(int, input_file.readline().split())
verify_constraints(N, K)

d = [0] * (K + 1)
t = [0] * (K + 1)

for i in range(1, K + 1):
    d[i], t[i] = map(int, input_file.readline().split())

for i in range(1, K):
    t[i + 1] = min(t[i + 1], t[i] + (d[i + 1] - d[i]) * T)

for i in range(K - 1, 0, -1):
    t[i] = min(t[i], t[i + 1] + (d[i + 1] - d[i]) * T)

res = 0
for i in range(1, K):
    l, r = max(t[i], t[i + 1]), 1 * N * T
    tmp = 0
    while l <= r:
        m = (l + r) // 2
        if try_time(m, i):
            l = m + 1
            tmp = m
        else:
            r = m - 1
    res = max(res, tmp)

res = max(res, max(t[K] + (N - d[K]) * T, t[1] + (d[1] - 1) * T))
output_file.write(str(res))

input_file.close()
output_file.close()