Cod sursa(job #2908661)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 4 iunie 2022 21:08:19
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

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

int a[400001];

int main()
{
    int n;
    in >> n;

    for (int i=1; i<=n; i++)
    {
        in >> a[i];
        bool culoare;
        in >> culoare;
        if (!culoare)
            a[i] = -a[i];
        a[n+i] = a[i];
    }

    int sum = 0, pos = 0, len = 0;
    int maxim = -1e9, P = 0, L = 0;

    for (int i=1; i<=n+n; i++)
    {
        if (sum >= 0)
            {
                if (len == n)
                {
                    sum -= a[i--];
                    len--;
                    continue;
                }
                sum += a[i];
            }
        else
        {
            sum = a[i];
            pos = i;
            len = 0;
        }
        len++;

        if (sum > maxim)
        {
            maxim = sum;
            P = pos;
            L = len;
        }
        else if (sum == maxim)
        {
            if (pos == P)
                L = min(L, len);
            else if (pos < P)
                P = pos, L = len;
        }
    }

    out << maxim << ' ' << P << ' ' << L;

    return 0;
}