Cod sursa(job #1718186)

Utilizator cristina_borzaCristina Borza cristina_borza Data 16 iunie 2016 22:35:27
Problema Buline Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <deque>

#define INF 1000000
#define DIM 500000

using namespace std;

ifstream f("buline.in");
ofstream g("buline.out");

int n , type , pos , mx = - INF, lg;
int v[DIM] , sum[DIM];

deque <int> coada;

int main() {
    f >> n;
    for (int i = 1; i <= n; ++i) {
        f >> v[i] >> type;
        if (!type) {
            v[i] = -v[i];
        }
    }

    for (int i = 1; i <= n; ++i) {
        v[n + i] = v[i];
    }

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

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

        if (sum[i] - sum[coada.front()] > mx) {
            mx = sum[i] - sum[coada.front()];
            pos = coada.front() + 1;
            lg = i - coada.front();
        }

        else
            if (sum[i] - sum[coada.front()] == mx) {
                int qq = coada.front() + 1;
                if (pos > qq) {
                    pos = qq;
                    lg = i - coada.front();
                }

                else {
                    if (pos == qq)
                        lg = min(lg , i - coada.front());
                }
            }

        while (coada.empty() && sum[coada.back()] > sum[i]) {
            coada.pop_back();
        }

        coada.push_back(i);
    }

    g << mx << " " << pos << " " << lg;
    return 0;
}