37ος ΠΔΠ Α' Φάση
Πρόσληψη πιτσαδόρων (hiring)
Ο Τάκης το πήρε τελικά απόφαση να προσλάβει εργαζόμενους. Μάλιστα, έχει βρει \(N\) υποψήφιους πιτσαδόρους. Κάθε υποψήφιος μπορεί να προσληφθεί με το πολύ ένα είδος συμβολαίου: χάλκινο, ασημένιο ή χρυσό. Ο προϋπολογισμός του Τάκη του επιτρέπει να προσφέρει μέχρι \(X\) χάλκινα, μέχρι \(Y\) ασημένια και μέχρι \(Z\) χρυσά συμβόλαια. Επιπλέον, ο ίδιος έχει φροντίσει να ισχύει ότι \(X+Y+Z \geq N\).
Ανάλογα με το συμβόλαιο που λαμβάνει ένας πιτσαδόρος αποδίδει διαφορετικά. Αν στον \(i\)-οστο πιτσαδόρο προσφερθεί χάλκινο συμβόλαιο, αυτός θα έχει απόδοση \(A_i\), αν του προσφερθεί ασημένιο θα έχει απόδοση \(B_i\) και αν του προσφερθεί χρυσό θα έχει απόδοση \(C_i\). Για όλους τους υποψηφίους ισχύει ότι \(Α_i \leq B_i \leq C_i\), δηλαδή όταν προσφέρουμε συμβόλαιο υψηλότερης βαθμίδας η απόδοση πάντα βελτιώνεται.
Προφανώς, ο Τάκης θέλει να μεγιστοποιήσει την συνολική απόδοση των πιτσαδόρων του, δηλαδή το άθροισμα των αποδόσεων τους. Παρόλα αυτά, είναι απαραίτητο να παραμείνει εντός προϋπολογισμού. Να βρείτε την μέγιστη συνολική απόδοση που μπορεί να πετύχει ο Τάκης, τηρώντας τα όρια που έχει θέσει για κάθε είδος συμβολαίου.
Πρόβλημα
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, Java) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο hiring.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο hiring.out.
Δεδομένα εισόδου (hiring.in)
Η πρώτη γραμμή περιέχει τον αριθμό του υποπροβλήματος (βλ. παρακάτω). Η δεύτερη γραμμή περιέχει τέσσερις ακέραιους αριθμούς \(N\), \(X\), \(Y\) και \(Z\), χωρισμένους ανά δύο με ένα κενό διάστημα: το πλήθος των υποψηφίων, το μέγιστο πλήθος χάλκινων συμβολαίων, το μέγιστο πλήθος ασημένιων συμβολαίων και το μέγιστο πλήθος χρυσών συμβολαίων. Ακολουθούν \(N\) γραμμές καθεμία από τις οποίες αποτελείται από τρεις ακέραιους αριθμούς \(A_i\), \(B_i\) και \(C_i\), χωρισμένους ανά δύο με ένα κενό διάστημα: την απόδοση του \(i\)-οστου υποψηφίου αν του προσφερθεί χάλκινο, ασημένιο ή χρυσό συμβόλαιο, αντίστοιχα.
Δεδομένα ειξόδου (hiring.out)
Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: την μέγιστη συνολική απόδοση που μπορεί να πετύχει ο Τάκης αν προσφέρει μέχρι \(X\) χάλκινα, μέχρι \(Y\) ασημένια και μέχρι \(Z\) χρυσά συμβόλαια.
Παράδειγμα αρχείων εισόδου-εξόδου
| hiring.in | hiring.out |
|---|---|
| 1 5 3 1 1 3 6 8 1 1 2 4 9 12 3 5 7 9 9 9 |
31 |
Εξήγηση παραδείγματος:
Η καλύτερη επιλογή πιτσαδόρων είναι να δώσουμε ασημένιο συμβόλαιο στον πρώτο (απόδοση \(6\)), χάλκινο στον δεύτερο (απόδοση \(1\)), χρυσό στον τρίτο (απόδοση \(12\)), χάλκινο στον τέταρτο (απόδοση \(3\)) και χάλκινο στον πέμπτο (απόδοση \(9\)). Η συνολική απόδοση έτσι είναι \(6 + 1 + 12 + 3 + 9 = 31\).
Περιορισμοί
- \(1 \leq N \leq 100.000\),
- \(0 \leq X, Y, Z \leq N\),
- \(X + Y + Z \geq N\),
- \(1 \leq A_i \leq B_i \leq C_i \leq 1.000.000.000\).
Υποπροβλήματα
- (8 βαθμοί) \(N \leq 14\)
- (24 βαθμοί) \(Z = 0\)
- (3 βαθμοί) \(X = 0\)
- (12 βαθμοί) \(A_1 = A_2 = \ldots = A_N\) (οι αποδόσεις των χάλκινων συμβολαίων είναι όλες ίσες), \(B_1 \leq B_2 \leq \ldots \leq B_N\) (οι αποδόσεις των ασημένιων συμβολαίων βρίσκονται σε αύξουσα σειρά) και \(C_1 \geq C_2 \geq \ldots \geq C_N\) (οι αποδόσεις των χρυσών συμβολαίων βρίσκονται σε φθίνουσα σειρά).
- (20 βαθμοί) \(Z = 1\)
- (33 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί
Παρατηρήσεις
Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.