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

32ος ΠΔΠ B' Φάση Γυμνασίου
Πάμε πάλι διακοπές (longsumk)

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

Για κάθε μία από τις \(N\) μέρες του καλοκαιριού που μας ενδιαφέρουν, γνωρίζουμε ήδη την τιμή \(X_i\) του δωματίου τη μέρα \(i\) (όπου \(1 \le i \le N\)). Φυσικά, θέλουμε να πάμε όσο γίνεται περισσότερες μέρες διακοπές! Πόσο είναι το μεγαλύτερο συνεχόμενο διάστημα ημερών, τέτοιο ώστε το συνολικό κόστος του δωματίου αυτές τις μέρες να είναι ακριβώς ίσο με \(K\);

Πρόβλημα

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

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

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

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

Τα αρχεία εξόδου με όνομα longsumk.out είναι αρχεία κειμένου που αποτελούνται από μία μόνο γραμμή με έναν μόνο ακέραιο αριθμό: το μέγιστο πλήθος συνεχόμενων ημερών που μπορούμε να πάμε διακοπές με συνολικό κόστος διαμονής ακριβώς ίσο με \(K\). Αν αυτό δεν είναι εφικτό, θα πρέπει να εκτυπώνεται ο αριθμός μηδέν.

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

1o

longsumk.in longsumk.out
10 26
14 8 6 12 15 0 11 0 0 11
5

Στο πρώτο παράδειγμα, μπορούμε να πάμε διακοπές συνολικά για πέντε μέρες, πληρώνοντας \(15+0+11+0+0=26\).

2o

longsumk.in longsumk.out
7 48
29 7 17 9 17 10 5
0

Στο δεύτερο παράδειγμα δεν υπάρχει συνεχόμενο διάστημα ημερών με άθροισμα ακριβώς ίσο με \(48\).

Περιορισμοί

  • \(1 \leq N \leq 1.000.000\),
  • \(1 \leq K \leq 1.000.000.000\),
  • Το άθροισμα όλων των \(X_i\) δε θα υπερβαίνει το \(1.000.000.000\).

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

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