36ος ΠΔΠ Α' Φάση
Το σπίτι στον ελαιώνα (olivetrees)

Ο Βαγγέλης έχει ένα χωράφι με ελαιόδεντρα. Το χωράφι έχει σχήμα ορθογωνίου και μπορούμε να το φανταζόμαστε σαν ένα πλέγμα με \(N\) γραμμές και \(M\) στήλες. Τα ελαιόδεντρα είναι τοποθετημένα κατά μήκος των στηλών αρχίζοντας από τη νότια πλευρά του χωραφιού και κάθε ένα καταλαμβάνει ένα τετράγωνο του πλέγματος, όπως φαίνεται στο σχήμα που ακολουθεί. Άλλες στήλες έχουν περισσότερα και άλλες λιγότερα ελαιόδεντρα.

Στο παράδειγμά μας υπάρχουν \(N=6\) γραμμές και \(M=7\) στήλες. Η πρώτη στήλη έχει \(4\) ελαιόδεντρα, η δεύτερη έχει \(5\), η τρίτη έχει \(2\), η τέταρτη έχει \(1\), η πέμπτη έχει \(5\), η έκτη και η έβδομη έχουν από \(3\) ελαιόδεντρα.

Ο Βαγγέλης παρατηρεί ότι στο βόρειο τμήμα του χωραφιού του υπάρχει αρκετός χώρος που δεν είναι φυτεμένος με ελαιόδεντρα. Αποφασίζει λοιπόν να τον αξιοποιήσει, χτίζοντας εκεί το σπίτι του. Θέλει να βρει το ορθογώνιο με το μεγαλύτερο δυνατό εμβαδόν στο οποίο δε βρίσκεται κανένα ελαιόδεντρο. Στο παράδειγμά μας, το μεγαλύτερο σπίτι που μπορεί να χτίσει ο Βαγγέλης έχει διαστάσεις \(4 \times 2 = 8\) τετράγωνα του πλέγματος και φαίνεται στο παρακάτω σχήμα με καφέ χρώμα.

Πρόβλημα

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

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

Τα αρχεία εισόδου με όνομα olivetrees.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή υπάρχουν δύο ακέραιοι αριθμοί χωρισμένοι μεταξύ τους ένα κενό διάστημα: το πλήθος των γραμμών \(N\) και το πλήθος των στηλών \(M\). Η δεύτερη γραμμή περιέχει ακριβώς \(M\) ακέραιους αριθμούς \(T_i\) (όπου \(1 \leq i \leq M\)), χωρισμένους ανά δύο με ένα κενό διάστημα: το πλήθος των ελαιόδεντρων που έχει η \(i\)-οστή στήλη, για όλες τις στήλες κατά σειρά από αριστερά προς τα δεξιά.

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

Τα αρχεία εξόδου με όνομα olivetrees.out είναι αρχεία κειμένου με την εξής δομή. Πρέπει να περιέχουν ακριβώς μία γραμμή με ακριβώς έναν ακέραιο αριθμό: το μέγιστο δυνατό εμβαδόν του ορθογωνίου που δεν περιέχει κανένα ελαιόδεντρο.

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

• \(1 \leq N \leq 1.000.000\),
• \(1 \leq M \leq 1.000.000\),
• \(0 \leq T_i \leq N\) για κάθε \(i\), όπου \(1 \leq i \leq M\),
• Το συνολικό εμβαδόν του ελαιώνα (γινόμενο \(N \times M\)) δε θα υπερβαίνει τα \(2.000.000.000\).

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

1^o

olivetrees.in	olivetrees.out
6 7 4 5 2 1 5 3 3	8

Το πρώτο παράδειγμα αντιστοιχεί στα σχήματα των δύο προηγούμενων σελίδων. Το μεγαλύτερο ορθογώνιο που δεν καλύπτεται από ελαιόδεντρα έχει διαστάσεις \(4 \times 2 = 8\) τετράγωνα του πλέγματος.

2^o

olivetrees.in	olivetrees.out
1000 4 0 0 0 0	4000

Στο δεύτερο παράδειγμα, ο Βαγγέλης έχει έναν ελαιώνα που όμως δεν έχει κανένα ελαιόδεντρο. Επομένως, το μεγαλύτερο ορθογώνιο που μπορεί να βρει καλύπτει ολόκληρο τον ελαιώνα και το εμβαδόν του είναι \(1000 \times 4 = 4000\) τετράγωνα του πλέγματος.

Παρατηρήσεις:

Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.