Cod sursa(job #1829202)

Utilizator EpictetStamatin Cristian Epictet Data 14 decembrie 2016 16:02:40
Problema Buline Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>

using namespace std;

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

int n, best_sum, best_sum_pos_1, best_sum_lg, SUM[400010];
pair < int, int > minim;

int main()
{
    fin >> n;
    for (int aa, av, i = 1; i <= n; i ++)
    {
        fin >> av >> aa;
        if (!aa) av = -av;
        SUM[i] = SUM[i - 1] + av;
        SUM[i + n] = av;
    }
    for (int i = n + 1; i <= n * 2; i ++) SUM[i] += SUM[i - 1];

    minim = { 0, 0 };
    best_sum = SUM[1];
    for (int i = 2; i < n * 2; i ++)
    {
        if (i - minim.first == n + 1)
        {
            int j = minim.first + 1;
            minim = { j, SUM[j] };
            while (j < n)
            {
                if (minim.second > SUM[j])
                {
                    minim = { j, SUM[j] };
                }
                j ++;
            }
        }
        if (SUM[i] - minim.second > best_sum)
        {
            best_sum = SUM[i] - minim.second;
            best_sum_pos_1 = minim.first;
            best_sum_lg = i - minim.first;
        }
        if (minim.second > SUM[i])
        {
            minim = { i, SUM[i] };
        }
    }

    fout << best_sum << ' ' << best_sum_pos_1 + 1 << ' ' << best_sum_lg << '\n';
    fout.close();
    return 0;
}