Cod sursa(job #1307361)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 2 ianuarie 2015 00:21:12
Problema Buline Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 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,maxfin;
int s[nmax],nr[nmax],nr1,t[nmax];

int pot1,pot2,sol,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++)
                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

    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;

                    j=1;
                    sum=t[n]-t[i-1];
                    while (sum!=pot1) {
                            sum+=v[j];
                            j++;
                            lg++;
                    }
            }
            if (t[i]>maxuc) {
                    maxuc=t[i];
                    nr1=i;
            }
    }

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