Afişează mesaje
Pagini: [1]
1  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 399 Sum2 : August 11, 2019, 08:14:49
Nu înÈ›eleg de ce iau doar 50p  Brick wall ....
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;
}
Pagini: [1]
Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines