Cod sursa(job #1498662)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 8 octombrie 2015 21:58:17
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <deque>

#define lint long long int
using namespace std;

const int NMAX = 200005;

int v[2 * NMAX];
lint sums[NMAX];

deque <int> coada;

int main()
{
    ifstream cin("buline.in");
    ofstream cout("buline.out");

    int n = 0;
    cin >> n;

    bool _plus;
    for (int i = 1; i <= n; ++ i) {
        cin >> v[i] >> _plus;

        if (!_plus)
            v[i] *= (-1);
    }

    for (int i = 1; i <= n; ++ i)
        v[n + i] = v[i];
    for (int i = 1; i <= 2 * n; ++ i)
        sums[i] = v[i] + sums[i - 1];

    int best = v[1];
    int st = 0;
    int l = 1;

    coada.push_back(0);

    for (int i = 1; i < 2 * n; ++ i) {
        while (!coada.empty() && i - coada.front() > n)
            coada.pop_front();

        if (sums[i] - sums[coada.front()] > best) {
            best = sums[i] - sums[coada.front()];
            st = coada.front();
            l = i - coada.front();
        }
        else if (coada.front() < st) {
            st = coada.front();
            l = i - coada.front();
        }

        while (!coada.empty() && sums[coada.back()] > sums[i])
            coada.pop_back();
        coada.push_back(i);
    }

    cout << best << ' ' << st + 1 << ' ' << l << '\n';

    cin.close();
    cout.close();
    return 0;
}