29ος ΠΔΠ Καμπ (juniors)
Άθροισμα δύο άκρων (twoends)

Δίνεται μια ακολουθία \(N\) θετικών ακεραίων αριθμών. Ζητείται ο μεγαλύτερος δυνατός αριθμός \(S\), τέτοιος ώστε:

Να υπάρχουν \(X\) όροι στην αρχή της ακολουθίας που να έχουν άθροισμα \(S\).
Να υπάρχουν \(Y\) όροι στο τέλος της ακολουθίας που να έχουν άθροισμα \(S\).
Να είναι \(X + Y \leq N\), δηλαδή οι όροι που αθροίζουμε στα δύο άκρα να μην επικαλύπτονται.

Προσέξτε ότι το πρόβλημα έχει πάντα λύση (για \(S=0\) και \(X = Y = 0\)).

Γράψτε ένα πρόγραμμα που να διαβάζει την ακολουθία και να υπολογίζει το μέγιστο δυνατό τέτοιο \(S\).

Δεδομένα εισόδου (twoends.in)

Η πρώτη γραμμή της εισόδου θα περιέχει το πλήθος \(N\) των στοιχείων της ακολουθίας. Η δεύτερη γραμμή της εισόδου θα περιέχει \(N\) ακέραιους αριθμούς, χωρισμένους ανά δύο με ένα κενό διάστημα.

Δεδομένα εξόδου (twoends.out)

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό, το μεγαλύτερο δυνατό \(S\) με τις παραπάνω ιδιότητες.

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

1^o

twoends.in	twoends.out
7 3 2 5 7 1 6 4	10

Εξήγηση: Για το πρώτο παράδειγμα είναι \(3+2+5 = 6+4 (=10)\). Αυτό είναι το μεγαλύτερο δυνατό \(S\).

2^o

twoends.in	twoends.out
10 1 2 3 4 5 6 7 8 9 45	45

3^o

twoends.in	twoends.out
5 1 2 3 4 5	0

Περιορισμοί

Το άθροισμα όλων των όρων της ακολουθίας δεν υπερβαίνει το \(1.000.000.000\).
Mέγιστος χρόνος εκτέλεσης: \(3\) sec.
Mέγιστη διαθέσιμη μνήμη: \(128\) MB.

Υποπροβλήματα