32ος ΠΔΠ B' Φάση Λυκείου
Τα δύο καταστήματα (shops)
Μια επιχείρηση πρόκειται να ανοίξει δύο καταστήματα σε έναν μεγάλο εμπορικό δρόμο. Ο δρόμος αποτελείται από \(N\) τετράγωνα διατεταγμένα στη σειρά. Κάθε κατάστημα θα καλύπτει \(K\) διαδοχικά τετράγωνα και τα δύο καταστήματα μπορούν να επικαλύπτονται.
Η επιχείρηση γνωρίζει ότι κάθε τετράγωνο \(i\) (όπου \(1\leq{i}\leq{N}\)) αναμένεται να της αποφέρει κέρδος \(A_i\) εφόσον καλυφθεί από κάποιο κατάστημα - ακόμη κι αν καλυφθεί και από τα δύο καταστήματα, το συνολικό κέρδος που αποφέρει είναι και πάλι \(A_i\).
Πρόβλημα
Αναπτύξτε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο, αφού διαβάσει τις τιμές των \(N,K\) και \(A_i\) θα υπολογίζει το μέγιστο κέρδος που μπορεί να έχει η επιχείρηση ανοίγοντας δύο καταστήματα στον εμπορικό δρόμο, που καθένα καλύπτει \(K\) διαδοχικά τετράγωνα.
Αρχεία Εισόδου
Τα αρχεία εισόδου με όνομα shops.in είναι αρχεία κειμένου με την εξής δομή. Στην πρώτη γραμμή υπάρχουν δύο ακέραιοι αριθμοί \(N\) και \(K\), χωρισμένοι μεταξύ τους με ένα κενό διάστημα.Η δεύτερη γραμμή περιέχει \(N\) ακεραίους αριθμούς \(A_i\) (για \(1\leq{i}\leq{N}\)) χωρισμένους ανά δύο με κενό διάστημα: ο \(i\)-οστός αριθμός παριστάνει το αναμενόμενο κέρδος από το \(i\)-οστό τετράγωνο.
Αρχεία Εξόδου
Τα αρχεία εξόδου με όνομα shops.out είναι αρχεία κειμένου που αποτελούνται από μία και μόνο γραμμή με έναν μόνο ακέραιο αριθμό: το μέγιστο κέρδος που μπορεί να έχει η επιχείρηση ανοίγοντας δύο καταστήματα που καθένα καλύπτει \(K\) διαδοχικά τετράγωνα.
Παραδείγματα Αρχείων Εισόδου - Εξόδου:
1o
| shops.in | shops.out |
|---|---|
| 10 3 2 4 15 12 10 1 1 20 4 10 |
71 |
2o
| shops.in | shops.out |
|---|---|
| 10 3 1 5 20 20 20 15 10 1 1 1 |
90 |
Εξήγηση:
Στο πρώτο παράδειγμα, μπορούμε να τοποθετήσουμε το πρώτο κατάστημα ώστε να έχουμε κέρδος \(15+12+10\) και το δεύτερο έτσι ώστε να έχουμε κέρδος \(20+4+10\). Στο δεύτερο παράδειγμα, μπορούμε να τα τοποθετήσουμε έτσι ώστε το πρώτο κατάστημα να έχει κέρδος \(5+20+20\) και το δεύτερο να έχει κέρδος \(20+15+10\).
Περιορισμοί:
- \(3 \leq N \leq 2.000.000\),
- \(1 \leq K \leq \frac{N}{2}\),
- \(1 \leq A_i \leq 1.000.000\),
- Το άθροισμα όλων των \(A_i\) δε θα υπερβαίνει το \(1.000.000.000\).
- Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
- Μέγιστη διαθέσιμη μνήμη: \(64\) MB.
Παρατηρήσεις:
Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.