Pagini recente » Cod sursa (job #1612159) | Cod sursa (job #1578709) | Cod sursa (job #2513319) | Cod sursa (job #2869538) | Cod sursa (job #2588262)
#include <fstream>
#define NMAX 200005
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
long long v[2 * NMAX], s[2 * NMAX], dq[2 * NMAX], in = 1, sf = 1;
int main()
{
int n;
fin >> n;
for(int i = 1; i <= n; ++i){
int tip;
fin >> v[i] >> tip;
v[i] *= (tip == 0 ? -1 : 1);
s[i] = s[i - 1] + v[i];
}
for(int i = n + 1; i <= 2 * n; ++i){
v[i] = v[i - n];
s[i] = s[i - 1] + v[i];
}
dq[in] = 0;
int maxx = -10005, stF, lgF;
for(int i = 1; i <= 2 * n; ++i){
while(in <= sf && s[i] <= s[dq[sf]])
--sf;
dq[++sf] = i;
if(i - dq[in] - 1 == n)
++in;
if(s[i] - s[dq[in]] > maxx){
maxx = s[i] - s[dq[in]];
stF = dq[in] + 1;
lgF = i - dq[in];
}
}
fout << maxx << ' ' << stF << ' ' << lgF << '\n';
return 0;
}