Aflat in societatea sufletelor, Ichigo afla ca are de invins N inamici fiecare avand o putere cunoscuta. Dar desigur orice lupta are nevoie si de un plan. Ichigo a analizat toti inamicii si a descoperit 2 lucruri despre ei:
- Inamicii s-au aliniat in ordine de la cel mai slab pana la cel mai puternic (de la cel cu puterea cea mai mica pana la cel cu puterea cea mai mare). Totusi cu o noapte in urma inamicii au avut o petrecere si derutati ei si-au schimbat pozitiile dar nu cu mai mult de K de cea initiala (diferenta in modul intre pozitia initiala si cea finala sa fie maxim K).
- Ichigo a aflat deasemenea ca daca se lupta cu un inamic care are puterea P, atunci el in momentul respectiv trebuie sa aiba cel putin puterea P ca sa il poata invinge (in cazul in care ambii au puterea P, Ichigo castiga deoarece e personajul principal). Deasemenea in momentul in care Ichigo invinge un inamic care are puterea P atunci puterea lui va creste cu P (practic ii absoarbe puterea inamicului).
Ichigo trebuie sa afle puterea minima cu care poate porni astfel incat sa ii poata invinge pe toti inamicii stiind ca el se poate lupta cu ei in orice ordine vrea. Deoarece el nu este informatician el va roaga pe voi sa il ajutati.
Date de intrare
Fişierul de intrare bleach.in va contine pee prima linie 2 numere N si K cu semnificatia din enunt. Pe a doua linie se afla N numere reprezentand puterile celor N inamici. Al i-ulea numar reprezinta puterea inamicului care se afla pe pozitia i dupa petrecere.
Date de ieşire
Fisierul de ieşire bleach.out va contine un singur numar ce reprezinta puterea minima cu care trebuie sa porneasca Ichigo in lupta.
Restricţii
- 1 ≤ N ≤ 1.000.000
- 1 ≤ K ≤ 1000
- puterea unui inamic se va incadra in intervalul [1, 1.000.000.000]
- Pentru 20% din teste N ≤ 1000
- Pentru alte 20% din teste N ≤ 100.000
- Pentru alte 20% din teste 1 ≤ K ≤ 10
bleach.in
5 3
1 5 2 3 4
bleach.out
1
using namespace std;
ifstream f(“bleach.in”);
ofstream g(“bleach.out”);
long long n, k, i, j, pi, pstart, p;
priority_queue pq;
int main()
{
f >> n >> k;
for (i = 1; i <= k; i++) { f >> p;
pq.push(0-p);
}
for (i = k + 1; i <= n; i++) { f >> p;
pq.push(0-p);
p = pq.top();
pq.pop();
p = 0-p;
if (pi < p) {
pstart = pstart + (p – pi);
pi = p;
}
pi += p;
}
for (i = n + 1; i <= n + k; i++) {
p = pq.top();
pq.pop();
p = 0-p;
if (pi < p) {
pstart = pstart + (p – pi);
pi = p;
}
pi += p;
}
g << pstart;
f.close();
g.close();
return 0;
}