Cod sursa(job #2986685)

Utilizator NarcisMMic Narcis NarcisM Data 28 februarie 2023 22:16:38
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n, x1, x2, v[400000], s, p, l;
deque<int> d;
int main(){
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> x1 >> x2;
        v[i] = x1 * (x2 == 0 ? -1 : 1);
    }
    for(int i = n + 1; i < 2 * n; i++)
        v[i] = v[i - n];
    for(int i = 1; i < 2 * n; i++)
        v[i] += v[i - 1];
    for(int i = 1; i < 2 * n; i++){
        while(!d.empty() && d.front() <= i - n)
            d.pop_front();
        while(!d.empty() && v[d.back()] > v[i])
            d.pop_back();
        d.push_back(i);
        if(v[i] - v[d.front()] > s){
            s = v[i] - v[d.front()];
            p = d.front() + 1;
            l = i - d.front();
        }
    }
    fout << s << ' ' << p << ' ' << l;
    return 0;
}