Cod sursa(job #3289440)

Utilizator bagae123Burlacu Andrei bagae123 Data 26 martie 2025 20:37:38
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>

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

const int Nmax = 200000;
int v[2 * Nmax + 5];

int main()
{
    int n;
    fin >> n;
    int MinKadane=2e9;
    int MaxKadane=-2e9;
    int S1=0;
    int S2=0;
    int start1=1;
    int start2=1;
    int MaxKadanestart=1;
    int MinKadanestart=1;
    int length1,length2;
    int sum=0;
    for(int i=1; i<=n; i++)
    {
        int x;
        int p;
        fin>>x>>p;

        if(p==0)x=-x;
        sum+=x;
        if(S1<0)
        {
            S1=0;
            start1=i;
        }
        S1=S1+x;
        if(S1>MaxKadane)
        {
            MaxKadane=S1;
            MaxKadanestart=start1;
            length1=i-start1+1;
        }
        if(S2>0)
        {
            S2=0;
            start2=i;
        }
        S2=S2+x;
        if(S2<MinKadane)
        {
            MinKadane=S2;
            MinKadanestart=start2;
            length2=i-start2+1;
        }


    }
    int ComplementSum=sum-MinKadane,ComplementStart=(MinKadanestart+length2-1)%n+1,ComplementLength=n-length2;
    if(MaxKadane>ComplementSum)fout<<MaxKadane<<" "<<MaxKadanestart<<" "<<length1;
    else if(MaxKadane<ComplementSum)fout<<ComplementSum<<" "<<ComplementStart<<" "<<ComplementLength;
    else if(MaxKadanestart<ComplementStart)fout<<MaxKadane<<" "<<MaxKadanestart<<" "<<length1;
    else if(MaxKadanestart>ComplementStart)fout<<ComplementSum<<" "<<ComplementStart<<" "<<ComplementLength;
    else fout<<(length1<=ComplementLength?MaxKadane:ComplementSum)<<" "<<(length1<=ComplementLength?MaxKadanestart:ComplementStart)<<" "<<(length1<=ComplementLength?length1:ComplementLength);


    return 0;
}