32ος ΠΔΠ B’ Φάση Λυκείου
Τα δύο καταστήματα (shops)

Μια επιχείρηση πρόκειται να ανοίξει δύο καταστήματα σε έναν μεγάλο εμπορικό δρόμο. Ο δρόμος αποτελείται από $N$ τετράγωνα διατεταγμένα στη σειρά. Κάθε κατάστημα θα καλύπτει $K$ διαδοχικά τετράγωνα και τα δύο καταστήματα μπορούν να επικαλύπτονται.

Η επιχείρηση γνωρίζει ότι κάθε τετράγωνο $i$ (όπου $1\leqi\leqN$ ) αναμένεται να της αποφέρει κέρδος $Ai$ εφόσον καλυφθεί από κάποιο κατάστημα – ακόμη κι αν καλυφθεί και από τα δύο καταστήματα, το συνολικό κέρδος που αποφέρει είναι και πάλι $Ai$ .

Πρόβλημα

Αναπτύξτε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο, αφού διαβάσει τις τιμές των $N,K$ και $Ai$ θα υπολογίζει το μέγιστο κέρδος που μπορεί να έχει η επιχείρηση ανοίγοντας δύο καταστήματα στον εμπορικό δρόμο, που καθένα καλύπτει $K$ διαδοχικά τετράγωνα.

Αρχεία Εισόδου

Τα αρχεία εισόδου με όνομα shops.in είναι αρχεία κειμένου με την εξής δομή. Στην πρώτη γραμμή υπάρχουν δύο ακέραιοι αριθμοί $N$ και $K$ , χωρισμένοι μεταξύ τους με ένα κενό διάστημα.Η δεύτερη γραμμή περιέχει $N$ ακεραίους αριθμούς $Ai$ (για $1\leqi\leqN$ ) χωρισμένους ανά δύο με κενό διάστημα: ο i-οστός αριθμός παριστάνει το αναμενόμενο κέρδος από το $i$ -οστό τετράγωνο.

Αρχεία Εξόδου

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

Παραδείγματα Αρχείων Εισόδου – Εξόδου:

1^o

shops.in	shops.out
10 3 2 4 15 12 10 1 1 20 4 10	71

2^o

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$ .