Cod sursa(job #1829196)

Utilizator EpictetStamatin Cristian Epictet Data 14 decembrie 2016 15:53:54
Problema Buline Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>

using namespace std;

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

int n, best_sum, best_sum_pos_1, best_sum_pos_2, V[200010], SUM[400010];
pair < int, int > minim;


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

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

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