Αρχική > 27ος ΠΔΠ

27ος ΠΔΠ Γ' Φάση
Σουπερμάρκετ (supermarket)

[40 Μονάδες]

Ένα σουπερμάρκετ δίνει δωροεπιταγές στους πελάτες του με τον παρακάτω τρόπο. Ο πελάτης βάζει τα προϊόντα με μια σειρά στον ιμάντα του ταμείου και η ταμίας, όπως τα χρεώνει, όταν φτάσει στο προϊόν που βρίσκεται σε θέση πολλαπλάσια του αριθμού \(K\) δίνει μια δωροεπιταγή στον πελάτη ίσης αξίας με την τιμή αυτού του προϊόντος. Π.χ., για \(K=3\), δίνει δωροεπιταγές ίσες με την αξία του τρίτου προϊόντος, του έκτου, του ένατου, κ.ο.κ.

Ο Θανάσης έχει βάλει τα \(N\) προϊόντα που έχει αγοράσει στον ιμάντα με τυχαία σειρά και γνωρίζει ότι η τιμή του \(i\)-οστού προϊόντος (με τη σειρά που τα έχει βάλει) είναι \(A_i\). Τότε, πληροφορείται για τις δωροεπιταγές και μαθαίνει την τιμή του \(K\). Φυσικά, θα ήθελε να μεγιστοποιήσει τη συνολική αξία των δωροεπιταγών που θα πάρει. Δεν προλαβαίνει όμως να αναδιατάξει όλα τα προϊόντα του. Το μόνο που προλαβαίνει να κάνει είναι να τα διατρέξει μία φορά, ξεκινώντας από αυτό που είναι πλησιέστερα στο ταμείο, και (αν θέλει) να μετακινήσει κάποια προϊόντα στο τέλος της σειράς. Mπορεί όμως να κάνει το πολύ \(M\) τέτοιες μετακινήσεις και δεν μπορεί να μετακινήσει το ίδιο προϊόν δύο φορές.

Πρόβλημα

Nα γραφεί ένα πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο να διαβάζει τις τιμές των \(N\), \(M\) και \(K\), τις αξίες των προϊόντων \(A_i\) που θέλει να αγοράσει ο Θανάσης και να βρίσκει τη μέγιστη δυνατή συνολική αξία δωροεπιταγών που μπορεί να κερδίσει.

Aρχεία εισόδου

Τα αρχεία εισόδου με όνομα supermarket.in είναι αρχεία κειμένου αποτελούμενα από δύο γραμμές: Στην πρώτη γραμμή δίνονται τρεις ακέραιοι χωρισμένοι ανά δύο με ένα κενό διάστημα: οι τιμές των \(N\), \(M\) και \(K\) (\(1 \leq K \leq N \leq 100.000\), \(0 \leq M \leq 500\)). Στη δεύτερη γραμμή δίνονται \(N\) ακέραιοι αριθμοί \(A_i\) (\(1 \leq A_i \leq 10.000.000\)), χωρισμένοι ανά δύο με ένα κενό διάστημα: οι τιμές των προϊόντων με την αρχική σειρά. Το άθροισμα όλων των \(A_i\) δε θα υπερβαίνει το \(1.000.000.000\).

Aρχεία εξόδου

Τα αρχεία εξόδου με όνομα supermarket.out είναι αρχεία κειμένου αποτελούμενα από ακριβώς μία γραμμή που περιέχει ακριβώς έναν ακέραιο αριθμό: τη μέγιστη δυνατή συνολική αξία των δωροεπιταγών που θα πάρει ο Θανάσης.

Παραδείγματα αρχείων εισόδου - εξόδου

1ο:

supermarket.in supermarket.out
5 1 2
10 2 6 4 8
14

Εξήγηση: Στο πρώτο παράδειγμα, ο Θανάσης μπορεί να επιλέξει να μετακινήσει στο τέλος το πρώτο προϊόν (αξίας \(10\)) και έτσι η τελική σειρά με την οποία η ταμίας θα χρεώσει τα προϊόντα του να είναι \(2\), \(6\), \(4\), \(8\), \(10\). Επομένως, η συνολική αξία δωροεπιταγών που θα πάρει θα είναι \(6+8=14\). Αυτό είναι το μέγιστο δυνατό σε αυτή την περίπτωση.

2ο:

supermarket.in supermarket.out
5 2 2
10 1 1 1 10
11

Εξήγηση: Στο δεύτερο παράδειγμα, παρά το γεγονός ότι μπορεί να μετακινήσει δύο προϊόντα, ο Θανάσης δεν έχει κανένα τρόπο να βάλει τα προϊόντα του με τέτοια σειρά ώστε να πάρει δωροεπιταγές για τα δύο «δεκάρια». Ένας τρόπος να πάρει το μέγιστο δυνατό είναι να μετακινήσει έναν από τους «άσους» στο τέλος και έτσι η τελική σειρά να είναι \(10\), \(1\), \(1\), \(10\), \(1\). Τότε, η συνολική αξία δωροεπιταγών που θα πάρει θα είναι \(1+10=11\).

Βαθμολογία

Σε τουλάχιστον 25% των περιπτώσεων ελέγχου θα είναι \(M < N \leq 100\). Επίσης, σε όλες τις περιπτώσεις ελέγχου θα ισχύει (τουλάχιστον) ένα από τα παρακάτω:

  • \(N \leq 500\) και \(M \leq 500\)
  • \(N \leq 1.000\) και \(M \leq 300\)
  • \(N \leq 10.000\) και \(M \leq 100\)
  • \(N \leq 100.000\) και \(M \leq 10\)

Mορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.
Mέγιστος χρόνος εκτέλεσης: \(2\) sec.
Mέγιστη διαθέσιμη μνήμη: \(64\) MB.