399 Sum2

[•PlayLikeNeverB4]

Ti-am modificat sursa si acum ia 100. Ti-am trimis-o prin PM.

[•eudanip]

Ti-am modificat sursa si acum ia 100. Ti-am trimis-o prin PM.

Ar trebui sa ii spui si ce a gresit, nu numai sa ii modifici sursa si dupa sa ii o dai. Desigur, poate ai facut asta deja dar eu doar ma asiguram. 

[•PlayLikeNeverB4]

Daca are nelamuriri, va pune intrebari I-am zis ca nu e destul sa obtina punctajul maxim, ci sa si inteleaga programul.

[•ctlin04]

imi poate sugera si mie cineva care poate sa fie cauza, programul meu merge corect pe toate testele din comentarii, pe testul exemplu si pe toate testele mele, dar totusi obtin numai 10 puncte cu WA pe toate celelalte
Eu procedez astfel:
 1. tin un vector cu sume partiale maxime;
 2. tin alt vector cu lungimile de segvente din care se obtin aceste sume partiale maxime;
 3. parcurg elementele de la 1..n, si aleg elementul care are lungimea cuprinsa intre L si U, si are valoare maxima in vectorul cu sume, acest element fiind solutia.

[•maritim]

Nu este chiar ok solutia !

Ideea e ca subsecventa de suma maxima se mai poate face si ca maximul dintre A[ i ] - cea mai mica suma partiala pe pozitii anteriaore lui i . Dupa ce observi asta poti deduce usor cum trebuie sa faci mai departe in acest caz .

[•ctlin04]

poate imi explici remarca dupa exemplu dat, pur si simplu spune terog cum trebue sa procedez in cazul dat:
vectorul : 100  -100 0 -5 0 10 0 1
v. cu sum: 100 -100 0 -5 11 11 1 1
v. cu lung:  1      1   1   1 4   3  2  1
Cam asa construesc eu vectorii pe care i-am enuntat mai sus.

[•maritim]

Sumele partiale sunt sumele de pe pozitia 1 la i:

vectorul: 100  -100 0 -5 0 10 0 1
vectorul cu sume: 100 0 0 -5 0 5 5 6

Subsecventa de suma maxima ce se termina pe pozitia i = 8 este:
ssm[ 8 ] = Sum[ 8 ] - min(Sum[8],Sum[7] ... Sum[1]) = 6 - (-5) = 11, ceea ce si este !

ssm pentru fiecare: 100 0 0 -5 0 10 10 11

Acum ar trebui sa fie usor sa deduci cum se rezolva problema !

[•ctlin04]

ms mult Andrei Cristian, explicatia ta chiar m-a ajutat inca nu am luat punctaj maxim dar oricum sunt multumit ca am scapat de WA, acum sunt sigur ca merg pe o abordare corecta si trebue doar sa ma gindesc la optimizari.

[•ctlin04]

stiu ca deja sunt plictisitor, dar mai am o ultima intrebare; mai este ceva special la aceasta problema? am facut optimizarile necesare si imi intra toate testele in timp, numai ca totusi am WA pe 3 teste, am mai vazut in surse asa situatii, cei care au rezolvat aceasta problema poate imi spuneti si mie, despre ce este vorba

[•tzipleatud]

Cred ca ar trebui imbunatatite testele pentru ca cu o sursa de 100 p pe testul:
3 3 3
10 -1000 10000
 imi da raspunsul 10000.

[•Bit_Master]

Un subsir format din elemente consecutive ale sirului initial nu e o subsecventa?

[•PlayLikeNeverB4]

Ba da, dar daca o formulezi asa atunci nu mai trebuie sa explici ce e o subsecventa. Poate de aceea e scris asa.

[•Theory]

E o mica problema cu testele. Am trimis o sursa in care nu tineam cont de lungimea minima a secventei si am luat 100

[•NicuCJ]

Iau 90 puncte cu WA pe testul 8. Folosesc un multiset in care bag la fiecare pas s[i+U-1] si scot s[i+L-2] (s fiind sume partiale). Nu inteleg ce ar putea fi gresit ?.

[•PlayLikeNeverB4]

Nu tratezi cazul in care maximul e un numar negativ. 

[•NicuCJ]

Intr-adevar, dar se pare ca nu asta e problema. Am initializat maxim cu maxim=-10000000000000LL; si tot WA iau. Mersi pentru raspunsul prompt oricum

[•PlayLikeNeverB4]

O alta problema pe care o ai e ca tu verifici maximul doar daca poti sa adaugi un element nou in dreapta, dar nu tratezi subsecventele mai scurte. Vezi testul asta

Cod:

5 2 4
-1000 -1000 -1000 1000 1000

[•NicuCJ]

Asta era! Mersi mult

[•alecsandru]

60 pe wrong answer. Aparent am uitat un caz.

[•uvIanis]

Nu înÈ›eleg de ce iau doar 50p  ....
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;
}