Cod sursa(job #1741707)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 14 august 2016 20:39:26
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <iomanip>
#include <queue>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <set>
#include <map>
using namespace std;

const int MAXN = 200000;

int v[1 + 2 * MAXN];
long long sum[1 + 2 * MAXN];
deque<int> Deque;

int main() {
    ifstream cin("buline.in");
    ofstream cout("buline.out");
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int color;
        cin >> v[i] >> color;
        if (!color)
            v[i] *= -1;
        v[i + n] = v[i];
    }
    for (int i = 1; i <= 2 * n; i++)
        sum[i] = sum[i - 1] + v[i];
    int position = 1, length = 1;
    long long maxSum = sum[1];
    Deque.push_back(1);
    for (int i = 2; i < 2 * n; i++) {
        if (Deque.front() < i-n)
            Deque.pop_front();
        if (sum[i] - sum[Deque.front()] > maxSum) {
            maxSum = sum[i] - sum[Deque.front()];
            position = Deque.front() + 1;
            length = i - Deque.front();
        }
        while (!Deque.empty() && sum[i] < sum[Deque.back()])
            Deque.pop_back();
        Deque.push_back(i);
    }
    cout << maxSum << " " << position << " " << length;
    return 0;
}