Pagini recente » Cod sursa (job #128198) | Cod sursa (job #1843358) | Cod sursa (job #2043441) | Cod sursa (job #449688) | Cod sursa (job #1401317)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
deque<int> d;
int main()
{
int n;
int v[400001], beg, f;
int s = -100000;
fin >> n;
int x1, x2;
for (int i = 1; i <= n; ++i)
{
fin >> x1 >> x2;
if (x2 == 0)v[i] = x1 * -1;
else v[i]= x1;
}
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 (s <v[i] -v[d.front()])
{
s = v[i] - v[d.front()];
f = i - d.front();
beg = d.front()+ 1;
}
}
fout << s << ' ' << beg << ' ' << f;
}