Ο έρανος

5

1 votes
Hard
Problem

Ο Παντελής προσπαθεί να μαζέψει λεφτά για το ταμείο πρόνοιας του σχολείου του. Στην γειτονιά του υπάρχουν Ν σπίτια στη σειρά, το ένα μετά το άλλο. Κάποια σπίτια δίνουν λεφτά στον Παντελή ενώ κάποια άλλα όχι. Αν ο Παντελής επισκεφτεί αρχικά το σπίτι στη θέση m το κοντινότερο σπίτι που μπορεί να επισκεφτεί ο Παντελής θα είναι το σπίτι που βρίσκεται στη θέση m+K+1. Να βρείτε το μέγιστο ποσό που μπορεί να μαζέψει ο Παντελής από τον έρανο.

Δεδομένα εισόδου

  • Στην πρώτη γραμμή εμφανίζεται ένας θετικός ακέραιος αριθμός Τ (1<=Τ<=250), το πλήθος των αρχείων ελέγχου (testcases).
  • Για κάθε ένα από τα αρχεία ελέγχου θα εμφανίζονται:
    - Δύο θετικοί ακέραιοι αριθμοί Ν (1<=Ν<=10000) και Κ (0<=K<=Ν-1). Το πλήθος των σπιτιών και η απόσταση που πρέπει να έχουν μεταξύ τους.
    - Ν ακέραιοι αριθμοί στο διάστημα -10^9 ≤ xi ≤ 10^9, το ποσό που θα δώσει κάθε σπίτι για τον έρανο. Θετικοί αριθμοί σημαίνει ότι το σπίτι δίνει το αντίστοιχο ποσό ενώ αρνητικοί αριθμοί ή μηδέν σημαίνει ότι το σπίτι δεν δίνει λεφτά για τον έρανο.

Δεδομένα εξόδου

Σε κάθε γραμμή, θα εμφανίζεται ένας ακέραιος αριθμός W (W>=0), το μέγιστο ποσό που μπορεί να μαζέψει ο Παντελής.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Ο Παντελής θα επισκεφτεί κατά σειρά τα σπίτια στη θέση 1 (5), θέση 3 (2) και στη θέση 6 (1), με συνολικό ποσό 5+2+1=8. Να σημειωθεί ότι ο Παντελής αφού επισκεφτεί το σπίτι στη θέση 1 (5) δεν μπορεί να επισκεφτεί το σπίτι στη θέση 2 (4) γιατί δεν βρίσκεται σε απόσταση Κ+1 σπίτια από το προηγούμενο.

Editor Image

?