23ος ΠΔΠ Καμπ (κοινά)
Εστιατόρια (restaurants)

Ως υπεύθυνος δικτύου μιας αλυσίδας εστιατορίων, πρέπει να επιλέξετε πού θα ανοίξουν καταστήματα κατά μήκος της νέας εθνικής οδού. Έχουν προεπιλεγεί \(N\) υποψήφιες θέσεις και μπορούν να ανοίξουν καταστήματα σε οσεσδήποτε από αυτές. Για κάθε υποψήφια θέση \(1 \leq i \leq N\) έχει υπολογισθεί το αναμενόμενο κέρδος από το κατάστημα που μπορεί να ανοίξει εκεί, με βάση αν θα ανοίξουν καταστήματα στις γειτονικές θέσεις. Αν δεν ανοίξει κατάστημα σε καμία από τις θέσεις \(i-1\) και \(i+1\), το αναμενόμενο κέρδος από το κατάστημα στην θέση \(i\) είναι \(a_i\), αν ανοίξει κατάστημα σε μία από τις θέσεις \(i-1\) και \(i+1\), το αναμενόμενο κέρδος είναι \(b_i\), και αν ανοίξουν καταστήματα και στις δύο θέσεις \(i-1\) και \(i+1\), το αναμενόμενο κέρδος είναι \(c_i\) (τα \(c_1\) και \(c_N\) δεν ορίζονται, και για κάθε θέση \(i\), ισχύει ότι \(a_i \geq b_i \geq c_i \geq 0\)). Γράψτε ένα πρόγραμμα που να επιλέγει τις θέσεις όπου πρέπει να ανοίξουν τα καταστήματα μεγιστοποιώντας το κέρδος.

Αρχεία Εισόδου (restaurants.in):

Η πρώτη γραμμή της εισόδου θα περιέχει το πλήθος των υποψήφιων θέσεων \(N\). Η δεύτερη γραμμή περιέχει \(N\) αριθμούς, τις τιμές των \(a_1, \ldots , a_N\). Η τρίτη γραμμή περιέχει \(N\) αριθμούς, τις τιμές των \(b_1, \ldots , b_N\). Τέλος, η τέταρτη γραμμή περιέχει \(N-2\) αριθμούς, τις τιμές των \(c_2, \ldots , c_{N-1}\).

Αρχεία Εξόδου (restaurants.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό, το μέγιστο κέρδος που μπορεί να επιτευχθεί.

Παράδειγμα Αρχείου Εισόδου - Εξόδου:

restaurants.in	restaurants.out
8 10 9 15 8 18 12 6 8 6 5 8 7 16 10 5 7 3 6 6 12 9 4	61

Εξήγηση παραδείγματος: Η βέλτιστη λύση είναι να ανοίξουν εστιατόρια στις θέσεις \(1\), \(3\), \(5\), \(6\), \(7\), και \(8\). Έτσι το αναμενόμενο κέρδος είναι \(61\) (\(10+0+15+0+16+9+4+7\)).

Περιορισμοί:

• \(2 \leq N \leq 1.000.000\).
• \(0 \leq c_i \leq b_i \leq a_i \leq 1.000\).
• Όριο χρόνου εκτέλεσης: \(2\) sec.
• Όριο μνήμης: \(64\) MB.