Cod sursa(job #2930834)

Utilizator gabriel.9619Gabriel Stefan Tita gabriel.9619 Data 29 octombrie 2022 17:58:48
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
/*#include <fstream>
#include <climits>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int v[200001];
int main()
{
    int n, i, culoare, x, inc, l, incmax, lmax, j;
    long long s=LLONG_MIN, smax=LLONG_MIN;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>culoare;
        if(culoare==0)
        {
            v[i]=-x;
        }
        else
        {
            v[i]=x;
        }
    }
    s=0;
    for(i=1;i<=n*2;i++)
    {
        if(i>n)
        {
            j=i%n;
        }
        else
        {
            j=i;
        }
        if(s+v[j]>=0)
        {
            s+=v[j];
            l++;
        }
        else
        {
            inc=j;
            s=v[j];
            l=1;
        }
        if(s>smax)
        {
            smax=s;
            incmax=inc;
            lmax=l;
        }
    }
    fout<<smax<<" "<<incmax<<" "<<lmax;
    return 0;
}*/
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int v[400001];
int main()
{
    int n, i, culoare, x, inc, l=0, incmax=0, lmax=0, j;
    long long s=INT_MIN, smax=INT_MIN;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>culoare;
        if(culoare==0)
        {
            v[i]=-x;
        }
        else
        {
            v[i]=x;
        }
    }
    for(i=n+1;i<=2*n;i++)
    {
        v[i]=v[i-n];
    }
    s=v[1];
    inc=1;
    l=1;
    for(i=2;i<=n*2;i++)
    {
        if(s+v[i]>=v[i])
        {
            s+=v[i];
            l++;
        }
        else
        {
            s=v[i];
            l=1;
            inc=i;
        }
        if(s>smax)
        {
            smax=s;
            incmax=inc;
            lmax=l;
        }
        if(l==n)
        {
            l--;
            inc++;
            s=s-v[i-n+1];
        }
    }
    fout<<smax<<" "<<incmax<<" "<<lmax;
}