Cod sursa(job #455201)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 13 mai 2010 10:33:54
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<fstream>
#define inf "buline.in"
#define outf "buline.out"
#define NMax 200100
#define INF 0x3f3f3f3f
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int N;
int v[NMax],v2[NMax];
int sum=0;

void read()
{
int a,b;
f>>N;
for(int i=1; i<=N; i++)
    {
    f>>a>>b;
    if( !b ) v[i]=-a;
    else v[i]=a;
    v2[i]=-v[i];
    sum += v[i];
    }
}

int scmax(int a[],int &pm,int &lm)
{
int smax,s,p,l;
smax = s = a[1];
p = pm = 1 ; l = lm = 1 ;
for(int i=2; i<=N; i++)
    {
    if( s<0 )
        {
        s = a[i];
        p = i;
        l = 1;
        }
    else s += a[i], l++;
    if( s>smax ) smax=s, pm=p, lm=l;
    else if( s==smax )
        {
        if( p+l<pm+lm ) pm=p , lm=l;
        else if( p+l==pm+lm && N-l<N-lm ) pm=p,lm=l;
        }
    }
return smax;
}

void solve()
{
int p,l;
int s;
s = scmax(v2,p,l);
//g<<s<<"\n";
g<< sum+s <<" "<< p+l <<" "<< N-l ;
}

int main()
{
read(); solve();
f.close(); g.close();
return 0;
}