Cod sursa(job #1307366)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 2 ianuarie 2015 00:43:12
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#include <fstream>
#define nmax 200005
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,v[nmax];
int maxuc=-(1<<30),maxfin;
int s[nmax],nr[nmax],nr1,t[nmax];

int pot1,pot2,sol=(-1<<30),poz,lg,sum;

int main() {

    int i,j;
    f>>n;
    for (i=1;i<=n;i++) {
        f>>v[i]>>j;
        if (j==0) v[i]=-v[i];
    }
    //precalculez de la inceput
    for (i=1;i<=n;i++)
                s[i]=s[i-1]+v[i];
    for (i=1;i<=n;i++){
                if (s[i]>s[i-1]) nr[i]=i;
                            else nr[i]=nr[i-1];
                s[i]=max(s[i-1],s[i]);
    }

    //precalculez catre final
    for (i=1;i<=n;i++) t[i]=t[i-1]+v[i];
    //gasesc solutiile
    if (t[n]>maxuc){
            maxuc=t[n];
            nr1=n;
    }
    for (i=n;i>=1;i--) {
            pot1=t[n]-t[i-1]+s[i-1];
            pot2=maxuc-t[i-1];


            if (pot2>=sol) {
                    sol=pot2;
                    poz=i;
                    lg=nr1-i+1;
            }
            if (pot1>=sol) {
                    sol=pot1;
                    poz=i;
                    lg=n-i+1+nr[i-1];
                    }

            if (t[i-1]>maxuc) {
                    maxuc=t[i-1];
                    nr1=i-1;
            }
    }

    g<<sol<<' '<<poz<<' '<<lg;
    return 0;
}