Salut! Nu am facut problema asta, dar cred ca iti pot raspunde la intrebarea ta in legatura cu deque. Avand in vedere ca fiecare element "creste" constant cu C, la fiecare pas, rezulta ca ordinea elementelor din deque nu se va modifica. Uite o portiune de cod:
#include <iostream>
#include <deque>
using namespace std;
int N,i,C,Y;
int A[1010];
deque<int> D;
int main ()
{
cin >> N >> C >> Y;
for (i=1; i<=N; i++)
cin >> A[i];
for (i=1; i<=N; i++)
{
while (!D.empty() && A[D.back()]+C*(i-D.back())<=A[i]) D.pop_back(); //scot cat timp A[i] reprezinta o solutie mai buna
while (!D.empty() && i-D.front()>Y) D.pop_front(); // scot cat timp solutia nu se afla in intervalul [X-Y,X]
D.push_back(i);
cout << "Maximul la pozitia " << i << " este " << (A[D.front()]+C*(i-D.front())) << '\n';
}
return 0;
}
Cam asa ceva ar veni, sper ca nu am gresit nimic. Bafta!