Fişierul intrare/ieşire:cadouri.in, cadouri.outSursăInfoPro, Etapa 3, Grupa B
AutorAlexandru PetrescuAdăugată dealexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu
Timp execuţie pe test0.6 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cadouri

Pentru că Lili a uitat să îi dea un cadou de Crăciun prietenei ei, Georgiana, s-a gândit să se revanşeze aducându-i cadouri timp de N zile. Astfel, în fiecare zi i din cele N, Lili va duce în faţa casei Georgianei cnti cadouri, toate de mărime mi. După cele N zile, Georgiana se apucă să sorteze cutiile cu cadouri în ordine crescătoare după mărime. Deoarece s-au strâns foarte multe cadouri, Georgiana te roagă să afli mărimea celui de al K-lea cadou după sortare. 

Date de intrare

Vă rugăm să consultaţi fişierul manager.cpp pe care îl puteţi găsi în ataşamente.

Date de ieşire

În fişierul de ieşire cadouri.out se va afişa un singur număr, mărimea celui de-al K-lea cadou în ordinea sortării.

Notă

Între ataşamente, puteţi găsi fişierul manager.cpp pe care îl puteţi descărca. E recomandat, atât pentru a scrie o sursa eficientă şi elegantă, cât şi pentru a simula experienţa problemei din timpul concursului, să completaţi această sursă cu implementarea funcţiei solve().

Restricţii

  • 1 ≤ N ≤ 5 000 000
  • 1 ≤ cnti, mi ≤ 109, pentru orice i de la 0 la N - 1
  •  $1 \leq K \leq \sum_{i=0}^{N-1} cnt_i$
  • Pe testele oficiale, şirurile cnt şi m sunt generate pseudo-random. Detaliile sunt ascunse concurenţilor.
  • Testele sunt grupate pe subtaskuri. Punctele pe un subtask sunt acordate doar dacă sursa trece toate testele din respectivul subtask. Punctajele pe subtaskuri diferă de cele din concurs.
  • Subtask 1, în valoare de 15 puncte,  $\sum_{i=0}^{N-1} cnt_i \leq 5\ 000\ 000$
  • Subtask 2, în valoare de 15 puncte, N ≤ 50 000
  • Subtask 3, în valoare de 15 puncte, K = 4
  • Subtask 4, în valoare de 30 puncte, 1 ≤ mi ≤ 3, pentru orice i de la 0 la N - 1
  • Subtask 5, în valoare de 25 puncte, fără restricţii suplimentare

Exemplu

cadouri.incadouri.out
5 7
3 2
4 3
2 1
2 2
1 1
2

Explicaţie

Mărimile cadourilor, după sortare, sunt:
1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3

Prin urmare cadoul al 7-lea în ordinea sortării are mărimea 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?