Pagini recente » Cod sursa (job #1604978) | Cod sursa (job #873429) | Cod sursa (job #2926377) | Cod sursa (job #1886517) | Cod sursa (job #1876151)
#include <fstream>
#include <iostream>
#include <deque>
#define inf 0x3f3f3f3f
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int d[2] = {-1,1}, v[400010], sum, poz, len,n;
deque < int > dq;
int main()
{
int x,y;
f >> n;
for(int i = 1; i <= n; ++i)
{
f >> y >> x;
v[i] = y * d[x] + v[i - 1];
v[i + n] = y * d[x];
}
for(int i = n + 1; i <= 2 * n ; ++i) v[i] += v[i - 1];
sum = v[1];
dq.push_back(1);
for(int i = 2; i <= 2 * n; ++i)
{
if(i - dq.front() > n) dq.pop_front();
if(v[i] - v[dq.front()] > sum)
{
sum = v[i] - v[dq.front()];
poz = dq.front() + 1;
len = i - dq.front();
}
while(!dq.empty() && v[i] < v[dq.back()]) dq.pop_back();
dq.push_back(i);
}
g << sum << ' ' << poz << ' ' << len << '\n';
}