Pagini recente » Cod sursa (job #1550776) | Cod sursa (job #770337) | Cod sursa (job #1121159) | Cod sursa (job #3213681) | Cod sursa (job #2548296)
#include <iostream>
#include <fstream>
#include <deque>
std::ifstream f("buline.in");
std::ofstream g("buline.out");
const int NMAX = 400'005;
int n,v[NMAX],op,s[NMAX],maxx,I,J;
std::deque<int>d;
int main(){
f >> n;
for(int i = 1;i <= n;++i){
f >> v[i] >> op;
if(op == 0)
v[i] = -v[i];
v[n + i] = v[i];
}
for(int i = 1;i <= 2 * n;++i)
s[i] = s[i - 1] + v[i];
maxx = -((1LL << 31) - 1);
d.push_back(1);
for(int i = 1;i <= 2 * n;++i){
while(!d.empty() && s[i] <= s[d.back()])
d.pop_back();
d.push_back(i);
if(i - d.front() == n)
d.pop_front();
if(s[i] - s[d.front()] > maxx){
maxx = s[i] - s[d.front()];
I = d.front() + 1;
J = i;
}
}
g << maxx << ' ' << I << ' ' << J - I + 1;
return 0;
}