Pagini recente » Cod sursa (job #516109) | Cod sursa (job #504086) | Cod sursa (job #2127350) | Cod sursa (job #2817936) | Cod sursa (job #3166152)
#include <bits/stdc++.h>
#define DIM 400001
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int v[DIM], sp[DIM];
deque <int> d;
int n, i, sign, Max = -1e9, start, len;
int main(){
fin >> n;
for(i=1;i<=n;i++){
fin >> v[i] >> sign;
v[i] *= (sign == 1) ? 1 : -1;
}
for(i=n+1;i<=2 * n;i++)
v[i] = v[i - n];
n *= 2;
// suma maxima cu lungime maxim n
for(i=1;i<=n;i++)
sp[i] = sp[i - 1] + v[i];
d.push_back(0);
for(i=1;i<=n;i++){
while(!d.empty() && sp[d.back()] > sp[i])
d.pop_back();
d.push_back(i);
if(i > n / 2){
while(!d.empty() && i - d.front() + 1 > n / 2)
d.pop_front();
}
if(Max < sp[i] - sp[d.front()]){
Max = sp[i] - sp[d.front()];
start = d.front() + 1;
len = i - d.front();
}
else if(Max == sp[i] - sp[d.front()] && i - d.front() < len){
start = d.front() + 1;
len = i - d.front();
}
}
fout << Max << " " << start << " " << len;
}