Cod sursa(job #2069686)

Utilizator dragos.galeteanu2001Dragos Iulian dragos.galeteanu2001 Data 18 noiembrie 2017 18:35:01
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
long int n, i, a, b, poz, P, P2, L, L2, j, v[400000], S[400000], Max[400000];
long long int mx=LONG_LONG_MIN, S_max, Suma;
int main()
{
    f>>n;
    for (i=0; i<n; i++) {
        f>>a>>b;
        if (b) v[i]=v[i+n]=a;
        else v[i]=v[i+n]=-a;
    }
    S[0]=v[0];
    for (S_max=Suma=v[0], P=poz=0, i=L=1; i<2*n; i++) {
        if (Suma<0) { Suma=v[i]; poz=i; }
        else { Suma+=v[i];
            if (S_max<Suma) { S_max=Suma; P=poz; L=i-poz+1; }
        }
        S[i]=Suma;
    }
    j=P;
    for (L=1, i=P+1; L<=n && i<n+P; i++)
        if (S[i]>mx) { mx=S[i]; L+=i-j; j=i; }

    S[0]=v[0];
    for (i=1; i<n; i++) S[i]=S[i-1]+v[i];
    Max[0]=S[0];
    for (i=1; i<n; i++) {
        if (S[i]>Max[i-1]) Max[i]=S[i];
        else Max[i]=Max[i-1]; }
    S_max=S[n-1]; P2=0;
    for (i=1; i<n; i++) {
        Suma=S[n-1]-S[i-1]+Max[i-1];
        if (Suma>S_max) { S_max=Suma; P2=i; }
    }

    if (S_max<mx) g<<mx<<' '<<P+1<<' '<<L;
    else g<<S_max<<' '<<P2+1<<' '<<n;
    f.close();
    g.close();
    return 0;
}