Cod sursa(job #895161)

Utilizator tangredonSilviu Georgescu tangredon Data 27 februarie 2013 10:18:36
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f ("buline.in");
ofstream g("buline.out");

int n;
int x[2*200002];
int s[2*200002];
int t[2*200002];
int l[2*200002];
int m,m2,m3;

void Read()
{
    int a,b;
    f >> n;
    for ( int i = 1; i <= n ; i++ )
    {
        f >> a >> b;

        if ( b == 1 )
            x[i] = a;
        else
            x[i]=- a;
    }

    for ( int i = 1; i <n ; i++ )
    {
        x[i+n] = x[i];
    }
}

int main()
{
    Read();
    s[1] = x[1];
    l[1] = 1;
    t[1] = 1;
    for ( int i = 2; i<= 2*n-1; i++ )
    {
        if ( s[i-1] + x[i] > x[i] )
        {
            s[i] = s[i-1] + x[i];
            l[i] = l[i-1] + 1;
            t[i] = t[i-1];
        }
        else
        {
            s[i] = x[i];
            l[i] = 1;
            t[i] = i;
        }

        if ( s[i] > m )
        {
            m = s[i];
            m2 = l[i]%n;
            m3 = t[i]%n;
        }
    }

    if (m3 == 0)
        m3 = n;
    g << m << ' ' << m2 << ' ' << m3;

}