Cod sursa(job #425391)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 25 martie 2010 18:26:55
Problema Buline Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<cstdio>
#include<fstream>
#include<vector>
#define pb push_back
#define INFI 2100000000
#define maxn 400005
using namespace std;

int n, smax, sum, ind, st, dr, v[maxn];

int main()
{
    int i, x;
    ifstream fin("buline.in");
    freopen("buline.out", "w", stdout);
    fin>>n;
    for(i=1;i<=n;++i)
    {
        int temp;
        fin>>x>>temp;
        if(temp==0)
            v[i]=-x;
        else
            v[i]=x;
    }
    for(i=n+1;i<=2*n;++i)
        v[i]=v[i-n];
    st=dr=ind=1;
    smax=-INFI;
    sum=v[1];
    for(i=2;i<=2*n;++i)
    {
        if(sum+v[i]<v[i])
            sum=v[i], ind=i;
        else
        {
            if(i-ind==n)
            {
                if(v[ind]<v[i])
                    sum-=v[ind], sum+=v[i], ind++;
                else
                {
                    ind++;
                    sum=v[ind];
                    i=ind;
                }
            }
            else
                sum+=v[i];
        }
        if(sum>smax)
            smax=sum, st=ind, dr=i;
    }
    printf("%d %d %d", smax, st, dr-st+1);
    return 0;
}