Pagini recente » Diferente pentru problema/s2c intre reviziile 16 si 36 | Cod sursa (job #3311390) | Cod sursa (job #1712312) | Cod sursa (job #152734) | Cod sursa (job #1427943)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n;
long long v[400000];
deque<int> d;
long long s, beg, lst;
int main()
{
fin >> n;
for (int i = 1, x1, x2; i <= n; ++i)
{
fin >> x1 >> x2;
v[i] = x1 * (x2 == 0 ? -1 : 1);
}
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 (v[i] - v[d.front()] > s)
{
s = v[i] - v[d.front()];
beg = d.front() + 1;
lst = i - d.front();
}
}
fout << s << ' ' << beg << ' ' << lst;
fin.close();
fout.close();
}