Pagini recente » Cod sursa (job #2721396) | Cod sursa (job #1826653) | Cod sursa (job #2478935) | Cod sursa (job #746958) | Cod sursa (job #503673)
Cod sursa(job #503673)
#include <fstream>
using namespace std;
int S[400001], St[400001], max;
int Poz[400001];
int i, j, N, NN, nr, cul;
int s1, s2, pmax, lmax;
ifstream in("buline.in");
ofstream out("buline.out");
void add(long long e, int pz)
{
while (s2 >= s1 && St[s2] > e) s2--;
s2++;
St[s2] = e;
Poz[s2] = pz;
if (pz - Poz[s1] + 1 > N) s1++;
}
int main()
{
long long max;
in>>N;
for (i = 1; i <= N; i++)
{
in>>nr>>cul;
if (cul == 0) nr = -nr;
S[i] = S[i - 1] + nr;
}
NN = N;
for (i = 1; i < N; i++)
S[++NN] = S[i] + S[N];
s1 = s2 = 0;
max = -2000001;
for (i = 1; i < NN; i++)
{
if (max < S[i] - St[s1])
{
max = S[i] - St[s1];
pmax = Poz[s1] + 1;
lmax = i - pmax + 1;
}
add(S[i], i);
}
out<<max<<" "<<pmax<<" "<<lmax;
return 0;
}