Cod sursa(job #3264042)

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

/**

dp[i] - suma maxima a unei secvente 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;
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        int x, c;
        cin >> x >> c;

        if (c == 0)
            a[i] = -x;
        else
            a[i] = x;
    }

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

    int ans = 0, ans_left, ans_right, st = 1, maxim = INT_MIN;

    dp[1] = a[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 (maxim > ans)
        {
            maxim = ans;
            ans_left = st, ans_right = i;
        }
    }

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

    for (int i = 1; i <= n-1; ++i)
    {
        int maxim = INT_MIN, st = i, left, right;
        dp[i] = a[i];
        for (int j = i+1; j <= n+i; ++j)
        {
            if (dp[j-1] + a[j] > a[j])
                dp[j] = dp[j-1] + a[j];
            else
            {
                st = j;
                dp[j] = a[j];
            }

            if (dp[j] > maxim)
            {
                left = st, right = j;
                maxim = dp[j];
            }
        }

        if (maxim > ans)
        {
            ans = maxim;
            ans_left = left, ans_right = right;
        }
    }

    cout << ans << " " << ans_left << " " << ans_right - ans_left + 1;
    return 0;
}