29ος ΠΔΠ Γ' Φάση
Πάω διακοπές (maketime)

Η Κατερίνα δουλεύει πολύ και χρειάζεται επειγόντως διακοπές. Θέλει να φύγει ταξίδι στα νησιά και να έχει όσο γίνεται περισσότερες συνεχόμενες μέρες για να ξεκουραστεί, μπορεί όμως να κάνει μόνο ένα ταξίδι. Έστω ότι οι μέρες είναι αριθμημένες από \(1\) έως και \(N\). Η Κατερίνα έχει στο πρόγραμμά της κάποιες υποχρεώσεις (συνολικά το πλήθος τους είναι \(M\)) τις οποίες έχει ήδη αναλάβει και που αντιστοιχούν σε κάποιες συγκεκριμένες μέρες: η \(i\)-οστή υποχρέωση είναι προγραμματισμένη για τη μέρα \(D_i\).

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

Πρόβλημα

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

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

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

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

Το αρχείο εξόδου με όνομα maketime.out είναι αρχείο κειμένου αποτελούμενο από μία γραμμή που θα περιέχει έναν ακέραιο αριθμό: το μέγιστο πλήθος ημερών που η Κατερίνα μπορεί να κάνει διακοπές.

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

1^o

maketime.in	maketime.out
10 5 2 6 9 3 2 7	5

Εξήγηση: Η Κατερίνα μπορεί να ακυρώσει τις υποχρεώσεις που έχει προγραμματίσει για τις μέρες \(2\) και \(3\). Έτσι, μπορεί να κάνει διακοπές από την \(1\)^η μέρα έως και την \(5\)^η, να έχει δηλαδή συνολικά \(5\) μέρες διακοπών.

2^o

maketime.in	maketime.out
12 4 1 4 10 4 8	5

Εξήγηση: Στο \(2\)^o παράδειγμα, η Κατερίνα μπορεί να ακυρώσει την υποχρέωση της μέρας \(8\) και να κάνει \(5\) μέρες διακοπών (από την \(5\)^η μέρα έως και την \(9\)^η). Προσέξτε ότι έχει προγραμματίσει δύο υποχρεώσεις για την \(4\)^η μέρα και δεν είναι διατεθειμένη να τις ακυρώσει και τις δύο (\(K=1\)).

2^o

maketime.in	maketime.out
7 2 0 3 4	3

Εξήγηση: Στο \(3\)^ο παράδειγμα, η Κατερίνα δεν είναι διατεθειμένη να ακυρώσει καμία υποχρέωση και μπορεί να κάνει \(3\) μέρες διακοπών, από την \(5\)^η μέρα έως και την \(7\)^η.

Περιορισμοί

• Για περιπτώσεις ελέγχου συνολικής αξίας \(20\%\), θα είναι: \(1 \leq N \leq 100\), \(1 \leq M \leq 100\), \(0 \leq K \leq M\)
• Για περιπτώσεις ελέγχου συνολικής αξίας \(50\%\), θα είναι: \(1 \leq N \leq 10.000\), \(1 \leq M \leq 20.000\), \(0 \leq K \leq M\)
• Για περιπτώσεις ελέγχου συνολικής αξίας \(100\%\), θα είναι: \(1 \leq N \leq 1.000.000\), \(1 \leq M \leq 2.000.000\), \(0 \leq K \leq M\)

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