Cod sursa(job #2571415)

Utilizator deiubejanAndrei Bejan deiubejan Data 4 martie 2020 23:03:08
Problema Buline Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <bits/stdc++.h>
using namespace std;

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

#define ll long long
#define x first
#define y second
#define en "\n"
#define sp " "

#define cin fin
#define cout fout
/*
*/

const int NMAX=2e5+10;
int n, s, x;
int v[NMAX];
int bestS, bestK, bestBegin, bestEnd;
int Begin, End;


void read()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i]>>x;
        if(x==0)
            v[i]*=-1;
    }
}

void solve()
{
    s=-1e7;
    bestS=-1e7;
    for(int i=1; i<=n; i++)
    {
        if(s<0)
        {
            ///schimbam inceputul si sfarsitul
            s = v[i];
            Begin = End = i;
        }
        else
        {
            s += v[i];
            End = i;
        }

        if(s > bestS)
        {
            bestS = s;
            bestK = End - Begin + 1;
            bestBegin = Begin;
            bestEnd = End;
        }
    }
    for(int i=1; i<Begin; i++)
    {
        if(s<=0)
            break;
        else
        {
            s += v[i];
            End = i;
        }

        if(s > bestS)
        {
            bestS = s;
            bestK = n - Begin + 1 + End;
            bestEnd = End;
        }
    }
    cout<<en<<bestS<<sp<<bestK<<sp<<bestBegin;
}


int main()
{
    int q=1;
    //cin>>q;
    while(q--)
    {
        read();
        solve();
    }

    return 0;
}