Pagini recente » Cod sursa (job #81565) | Cod sursa (job #81516) | Cod sursa (job #265634) | Cod sursa (job #588012) | Cod sursa (job #1603167)
#include <fstream>
#include <deque>
#include <algorithm>
#define NMAX 400001
using namespace std;
int main()
{
int N, i, x, y, v[NMAX], startIndex = 1, s = 0, smax = - (1 << 30), startPosition = 0, length = 0, partialSums[NMAX];
deque<int> dq;
ifstream f("buline.in");
f >> N;
for (i = 1; i <= N; i++)
{
f >> x >> y;
v[i] = y == 1 ? x : -x;
v[i + N] = v[i];
}
partialSums[0] = 0;
for (i = 1; i <= 2 * N - 1; i++)
{
partialSums[i] = partialSums[i - 1] + v[i];
}
f.close();
dq.push_back(1);
for (i = 2; i <= 2 * N - 1; i++)
{
while (i - dq.front() > N)
{
dq.pop_front();
}
if (partialSums[i] - partialSums[dq.front()] > smax)
{
smax = partialSums[i] - partialSums[dq.front()];
startIndex = dq.front() + 1;
length = i - dq.front();
}
while (!dq.empty() && partialSums[i] < partialSums[dq.back()])
{
dq.pop_back();
}
dq.push_back(i);
}
ofstream g("buline.out");
g << smax << " " << startIndex << " " << length;
g.close();
return 0;
}