Αρχική > 33ος ΠΔΠ

33ος ΠΔΠ Γ' Φάση
Ταξίδι στη Νέα Υόρκη (nytrip)

[40 Μονάδες]

Μετά την άρση των περιοριστικών μέτρων κατά του COVID-19, ο Μίλτος το δελφίνι αποφάσισε να κάνει δώρο στον εαυτό του ένα ταξίδι αναψυχής στην πανέμορφη Νέα Υόρκη και να θαυμάσει μερικούς από τους πιο εντυπωσιακούς και ιστορικούς ουρανοξύστες του κόσμου. Η ώρα φτάνει για το ταξίδι και οι μόνες αποσκευές του θα είναι το μαγιό του και η φωτογραφική του μηχανή.

Η Νέα Υόρκη είναι διάσημη για την “κορυφογραμμή των ουρανοξυστών” (Manhattan skyline). Σε αυτό το πρόβλημα, θα θεωρήσουμε ότι η κορυφογραμμή αποτελείται από \(N\) ουρανοξύστες που βρίσκονται ο ένας δίπλα στον άλλο σε μια γραμμή και ο καθένας έχει διαφορετικό ύψος \(H_i\) και πλάτος \(W_i\).

Ο Μίλτος θέλει να φωτογραφήσει την κορυφογραμμή έτσι ώστε να αποθανατιστούν όλοι οι ουρανοξύστες (καθένας ολόκληρος) σε μία η περισσότερες φωτογραφίες. Κάθε φωτογραφία που θα βγάλει μπορεί να καλύψει ένα τμήμα της κορυφογραμμής πλάτους \(L\) και, προφανώς, κάθε φωτογραφία πρέπει να χωράει τον ψηλότερο ουρανοξύστη στο αντίστοιχο τμήμα. Κατά την εκτύπωση των φωτογραφιών, ο Μίλτος δεν μπορεί να αλλάξει το πλάτος, μπορεί όμως να επιλέξει χαρτί κατάλληλου ύψους ώστε να χωράει ακριβώς ο ψηλότερος ουρανοξύστης.

Βοηθήστε τον Μίλτο να εξοικονομήσει όσο περισσότερο χαρτί γίνεται στην εκτύπωση. Βοηθήστε τον δηλαδή να βρει με ποιον τρόπο πρέπει να τραβήξει τις φωτογραφίες για να ελαχιστοποιήσει το συνολικό άθροισμα των υψών των ψηλότερων ουρανοξυστών κάθε φωτογραφίας.

Πρόβλημα:

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

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

Το αρχείο εισόδου με όνομα nytrip.in είναι αρχείο κειμένου. Η πρώτη γραμμή περιέχει δύο φυσικούς αριθμούς χωρισμένους με ένα κενό διάστημα: το πλήθος \(N\) των ουρανοξυστών και το πλάτος \(L\) που καλύπτει κάθε φωτογραφία. Κάθε μια από τις επόμενες \(N\) γραμμές περιέχει δύο φυσικούς αριθμούς \(H_i\) και \(W_i\), χωρισμένους με ένα κενό διάστημα: το ύψος και το πλάτος του i-οστού ουρανοξύστη.

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

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

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

nytrip.in nytrip.out
5 10
5 7
9 2
8 5
13 2
3 8
21
33pdp-c3

Εξήγηση: Έχουμε \(N=5\) ουρανοξύστες και κάθε φωτογραφία καλύπτει πλάτος \(L=10\). Το ελάχιστο δυνατό άθροισμα των υψών των ψηλότερων ουρανοξυστών από κάθε φωτογραφία το επιτυγχάνουμε τραβώντας 3 φωτογραφίες. Η πρώτη φωτογραφία θα περιέχει μόνο τον πρώτο ουρανοξύστη \((5,7)\). Η δεύτερη θα περιέχει τους επόμενους τρεις: \((9,2),(8,5),(13,2)\). Η τρίτη θα περιέχει μόνο τον τελευταίο \((3,8)\). Το άθροισμα των ψηλότερων ουρανοξυστών σε κάθε φωτογραφία είναι \(5+13+3=21\).

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

  • \(1 \leq N \leq 1.000.000, 1 \leq L \leq 1.000.000.000\)
  • \(1 \leq H_i \leq 1.000.000\)
  • \(1 \leq W_i \leq 1.000.000\) και \(W_i\leq L\)
  • Για περιπτώσεις ελέγχου συνολικής αξίας 11%, θα είναι \(1\leq N \leq 25\)
  • Για περιπτώσεις ελέγχου συνολικής αξίας 23%, θα είναι \(1\leq N \leq 1.000\)
  • Για περιπτώσεις ελέγχου συνολικής αξίας 41%, θα είναι \(1\leq N \leq 30.000\)

Προσοχή:

Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.

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