Cod sursa(job #29780)

Utilizator SpiriSpiridon Alexandru Spiri Data 9 martie 2007 22:27:17
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
using namespace std;
#define MAX 200002

int a[MAX];
int smax;
int n;

ifstream fin ("buline.in");
ofstream fout ("buline.out");

int main()
{
    fin >> n;
    int nr, se;
    for ( int i = 1; i <= n; i++ )
    {
        fin >> nr >> se;
        if ( se == 0 )
        {
             a[i] = -nr;
        }
        else
        {
            a[i] = nr;
        }
    }
    for ( int i = 1; i < n; i++ )
    {
        a[n+i] = a[i];
    }
    fin.close();
    
    int i1 = 1;
    int i;
    int j;
    smax = 0;
    int s = 0;
    for ( int k = 1; k < n + n; k++ )
    {
        if ( smax < s + a[k] )
        {
             smax = s + a[k];
             s+=a[k];
             i = i1;
             j = k;
        }
        else
        {
            if ( s + a[k] > 0 )
            {
                 s += a[k];
            }
            else
            {
                s = 0;
                i1 = k + 1;
            }
        }
    }
    fout << smax << " " << i << " " << j - i + 1;
    
    fout.close();
    return 0;
}