32ος ΠΔΠ Γ' Φάση
Άθροισμα λίγων (sumoffew)
[30 Μονάδες]
Μας δίνεται μία ακολουθία αποτελούμενη από \(N\) θετικούς ακέραιους αριθμούς \(x_1, x_2, \ldots, x_N\) και ένας φυσικός αριθμός \(K \le N\). Επιλέγουμε ένα συνεχόμενο διάστημα της ακολουθίας, έστω τους αριθμούς \(x_i, x_{i+1}, \ldots, x_j\) (για \(i \le j\)), μέσα στο οποίο όμως να μην εμφανίζονται περισσότεροι από \(K\) διαφορετικοί αριθμοί, και τους αθροίζουμε. Ποιο είναι το μέγιστο άθροισμα που μπορούμε να πετύχουμε με αυτόν τον τρόπο;
Πρόβλημα
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει τις τιμές των \(N\) και \(K\) καθώς και την ακολουθία των αριθμών και θα εκτυπώνει την απάντηση στο παραπάνω ερώτημα.
Αρχεία εισόδου
Το αρχείο εισόδου με όνομα sumoffew.in είναι αρχείο κειμένου με την εξής δομή. Η πρώτη γραμμή έχει δύο ακέραιους αριθμούς \(N\) και \(K\), χωρισμένους με ένα κενό διάστημα. Ο αριθμός \(N\) θα παριστάνει το πλήθος των αριθμών της ακολουθίας ενώ ο αριθμός \(K\) το μέγιστο επιτρεπτό πλήθος διαφορετικών αριθμών στο διάστημα που θα επιλέξουμε. Η επόμενη περιέχει \(N\) θετικούς ακέραιους αριθμούς, χωρισμένους ανά δύο με ένα κενό διάστημα: τους όρους της ακολουθίας.
Αρχεία εξόδου
Το αρχείο εξόδου με όνομα sumoffew.out είναι αρχείο κειμένου που περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: την απάντηση στο παραπάνω ερώτημα.
1o
| sumoffew.in | sumoffew.out |
|---|---|
| 10 1 9 5 5 5 5 5 9 9 9 17 |
27 |
Εξήγηση: Αφού \(K=1\), ψάχνουμε το διάστημα που αποτελείται από συνεχόμενες εμφανίσεις του ίδιου αριθμού και το οποίο έχει το μέγιστο άθροισμα. Τα τρία συνεχόμενα \(9\) δίνουν άθροισμα \(27\) και αυτή είναι η απάντηση εδώ.
2o
| sumoffew.in | sumoffew.out |
|---|---|
| 10 3 11 17 12 12 17 1 12 19 18 1 |
71 |
Εξήγηση: Εδώ \(K=3\). Στο διάστημα \(17, 12, 12, 17, 1, 12\) εμφανίζονται μόνο τρεις διαφορετικοί αριθμοί \((1, 12, 17)\). Το άθροισμα είναι \(17+12+12+17+1+12=71\). Δεν υπάρχει άλλο διάστημα με το πολύ τρεις διαφορετικούς αριθμούς και μεγαλύτερο άθροισμα.
3o
| sumoffew.in | sumoffew.out |
|---|---|
| 7 4 1 6 3 8 2 4 7 |
21 |
4o
| sumoffew.in | sumoffew.out |
|---|---|
| 9 4 1 2 3 2 3 1 3 1 2 |
18 |
Περιορισμοί
- Ισχύει \(1 \le K \le N \le 1.000.000\)
- Το άθροισμα όλων των \(x_i\) δε θα υπερβαίνει το \(1.000.000.000\).
- Για περιπτώσεις ελέγχου συνολικής αξίας 10%, θα είναι: \(1 \le N \le 1000\) και \(K=1\).
- Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι: \(1 \le N \le 1000\), δηλαδή η ακολουθία θα είναι σχετικά μικρή.
- Για περιπτώσεις ελέγχου συνολικής αξίας 70%, θα είναι: \(x_i \le 1.000.000\), δηλαδή οι όροι της ακολουθίας θα είναι σχετικά μικροί.
Προσοχή! Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.
Παρατηρήσεις:
- Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.
- Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
- Μέγιστη διαθέσιμη μνήμη: \(64\) MB.