Cod sursa(job #3268264)

Utilizator EricDimiericdc EricDimi Data 14 ianuarie 2025 10:55:18
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>

using namespace std;

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

const int INF = INT_MAX;
const int MAX_N = 200'000;

int v[MAX_N + 1], n;
long long sMax, pMax, lMax;
long long sMin, pMin, lMin;
long long s, p, l;
long long S;
bool flag;

int main()
{
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        f >> v[i] >> flag;
        if (!flag)
            v[i] = -v[i];
        S += v[i];
    }

    ///for (int i = 1; i <= n; i++)
    ///    cout << v[i] << ' ';
    ///cout << '\n';

    sMax = -INF;

    /// Cazul 1. Subsecventa de suma maxima este intre 1 si n

    s = sMax = v[1];
    l = lMax = 1;
    p = pMax = 1;

    for (int i = 2; i <= n; i++)
    {
        /// s = max(s + v[i], v[i]);
        if (s + v[i] > v[i]) /// if (s > 0)
        {
            s = s + v[i];
            l++;
        }
        else
        {
            s = v[i];
            p = i;
            l = 1;
        }
        if (s > sMax)
        {
            sMax = s;
            pMax = p;
            lMax = l;
        }
    }

    /// Cazul 2. Subsecventa de suma maxima incepe pe la sfarsitul sirului si se termina spre mijloc
    /// s = S - (v[l] + ... + v[r]) - maxima, deci (v[l] + ... + v[r]) - minima

    s = sMin = v[1];
    l = lMin = 1;
    p = pMin = 1;

    for (int i = 2; i <= n; i++)
    {
        /// s = min(v[i], s + v[i]);
        if (s + v[i] < v[i]) /// if (s > 0)
        {
            s = s + v[i];
            l++;
        }
        else
        {
            s = v[i];
            p = i;
            l = 1;
        }
        if (s < sMin)
        {
            sMin = s;
            pMin = p;
            lMin = l;
        }
    }

    s = S - sMin;

    if (s > sMax)
    {
        sMax = s;
        pMax = pMin + lMin;
        lMax = n - lMin;
    }

    g << sMax << ' ' << pMax << ' ' << lMax << '\n';

    f.close();
    g.close();
    return 0;
}