Cod sursa(job #2069604)

Utilizator dragos.galeteanu2001Dragos Iulian dragos.galeteanu2001 Data 18 noiembrie 2017 16:46:50
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
long int n, i, a, b, S_max, Suma, poz, P, L, mx=LONG_MIN, j;
int main()
{
    f>>n;
    long int v[200000], S[200000];
    for (i=0; i<n; i++) {
        f>>a>>b;
        if (b) v[i]=a;
        else v[i]=-a;
    }
    for (i=n; i<2*n; i++) v[i]=v[i-n];
    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; }
    g<<mx<<' '<<P+1<<' '<<L;
    f.close();
    g.close();
    return 0;
}