Cod sursa(job #2571146)

Utilizator deiubejanAndrei Bejan deiubejan Data 4 martie 2020 21:15:12
Problema Buline Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 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, total, start, val, type, bestk, s, k, st;
int v[NMAX];
pair<int, int>best;

void read()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>val>>type;
        if(type == 1)
            v[i]=val;
        else
            v[i]=-val;
    }
}

void solve()
{
    total=-1;
    for(int i=1; i<=n; i++)
    {
        if(total<=0)
        {
            total=v[i];
            start=i;
        }
        else
        {
            total+=v[i];
            if(best.x<total)
            {
                best.x=total;
                best.y=start;
            }
            else
            if(best.x==total)
                best.y=max(best.y, start);
        }
    }
    k=n-best.y+1;
    s=best.x;
    st=best.y;
    bestk=k;
    for(int i=1; i<st; i++)
    {
        best.x+=v[i];
        k++;
        if(best.x>s)
        {
            s=best.x;
            bestk=k;
        }
    }
    cout<<s<<sp<<st<<sp<<bestk;
}


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

    return 0;
}