Cod sursa(job #3264063)

Utilizator GabrielPopescu21Silitra Gabriel - Ilie GabrielPopescu21 Data 17 decembrie 2024 22:56:39
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;

/**
dp[i] - secventa de suma minima care se termina in i
*/

const int MAX = 6000005;
int a[MAX], dp[MAX];

int main()
{
    ifstream cin("buline.in");
    ofstream cout("buline.out");
    int n, total = 0, st = 1, raspSt, raspLen, len, maxim = INT_MIN;
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        int x, c;
        cin >> x >> c;
        a[i] = (c == 0) ? -x : x;
        total += a[i];
    }

    dp[1] = a[1], len = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (dp[i-1] + a[i] > a[i])
        {
            dp[i] = dp[i-1] + a[i];
            ++len;
        }
        else
        {
            st = i;
            len = 1;
            dp[i] = a[i];
        }

        if (dp[i] > maxim)
        {
            maxim = dp[i];
            raspSt = st;
            raspLen = len;
        }
    }

    for (int i = 1; i <= n; ++i)
        dp[i] = 0;

    int minim = INT_MAX, raspSt2, raspLen2;

    dp[1] = a[1], st = 1, len = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (dp[i-1] + a[i] < a[i])
            dp[i] = dp[i-1] + a[i];
        else
        {
            st = i;
            dp[i] = a[i];
        }

        if (minim > dp[i])
        {
            minim = dp[i];
            raspSt2 = i+1;
            raspLen2 = st - 1;
        }
    }

    if (maxim > total - minim)
        cout << maxim << " " << raspSt << " " << raspLen;
    else
        cout << total - minim << " " << raspSt2 << " " << (n+raspLen2) - raspSt2 + 1;

    return 0;
}