Cod sursa(job #2686100)

Utilizator un_fes_galbendaniel guba un_fes_galben Data 18 decembrie 2020 15:26:06
Problema Buline Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>

using namespace std;
int v[200005];
int sum[400005];
int negru[200005];
int main()
{
    ifstream cin("buline.in");
    ofstream cout("buline.out");
    int n,a,b,poz=1;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a>>b;
        if(b==1)
        {
            v[i]=a;
        }
        else
        {
            v[i]=-a;
            negru[poz]=i;
            poz++;
        }
    }
    sum[0]=v[0];
    for(int i=1; i<2*n; i++)
    {
        sum[i]=sum[i-1]+v[i%n];
    }
    int  max=-2100000000,suma=0,st,lung;
    if(poz==1)
    {
        max=sum[n-1];
        st=0;
        lung=n;
    }
    else
    {
        for(int i=1; i<poz; i++)
        {
            suma=0;
            for(int j=i+1; j<poz; j++)
            {
                suma=sum[negru[j]-1]-sum[negru[i]];
                if(suma>max)
                {
                    max=suma;
                    st=negru[i]+1;
                    lung=negru[j]-1-negru[i];
                }
            }
            for(int j=1; j<=i; j++)
            {
                suma=sum[negru[j]+n-1]-sum[negru[i]];
                if(suma>max)
                {
                    max=suma;
                    st=negru[i]+1;
                    lung=negru[j]-1+n-negru[i];
                }
            }
        }
    }
    cout<<max<<" "<<st+1<<" "<<lung<<'\n';
    return 0;
}