....Eu am rezolvat problema așa, mențin suma curentă și un deque în care introduc elementele în ordinea în care le citesc. Când citesc al i-lea element îl introduc în suma curentă și în deque și urmează cazurile:
- dacă lungimea deque-ului devine mai mare ca U atunci elimin obligatoriu primul element și fac update la sumă, compar cu suma maximă;
- dacă lungimea deque-ului este fix L atunci compar cu suma maximă;
- dacă lungimea deque-ului este mai mare decât L, atunci verific dacă eliminarea primului element din deque ar aduce o îmbunătățire la sumă. dacă da atunci fac update la sumă și elimin elementul; indiferent compar cu suma maximă.
COD:
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sum2.in");
ofstream fout("sum2.out");
int n, l, u, x, s{0}, smax {INT_MIN};
deque<int> dq;
int main()
{
fin>>n>>l>>u;
for(int i=1; i<=n; i++){
fin >> x;
dq.push_back(x);
s += x;
if(dq.size() > u) {
s -= dq.front();
dq.pop_front();
if(s > smax) smax = s;
}
if(dq.size() == l){
if(s > smax) smax = s;
}
if(dq.size() > l){
if(s - dq.front() > s) {
s -= dq.front();
dq.pop_front();
}
if(s > smax) smax = s;
}
}
fout<<smax;
}
