Cod sursa(job #3264051)

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

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;
        a[i] = (c == 0) ? -x : x;
    }

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

    int ans = INT_MIN, ans_left = 0, ans_right = 0, st = 1;
    dp[1] = a[1];
    for (int i = 1; i <= 2 * n - 1; ++i)
    {
        if (i > 1 && dp[i - 1] + a[i] > a[i])
            dp[i] = dp[i - 1] + a[i];
        else
        {
            dp[i] = a[i];
            st = i;
        }

        if (dp[i] > ans && (i - st + 1) <= n)
        {
            ans = dp[i];
            ans_left = st;
            ans_right = i;
        }
    }

    cout << ans << " " << (ans_left) % n << " " << ans_right - ans_left + 1 << "\n";

    return 0;
}