Pagini recente » Cod sursa (job #2718222) | Cod sursa (job #1466903) | Cod sursa (job #899602) | Cod sursa (job #702870) | Cod sursa (job #934708)
Cod sursa(job #934708)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <deque>
#include <iterator>
#include <limits>
#include <cstring>
#define MAXN 400003
using namespace std;
long long vec[MAXN];
long long sums[MAXN];
int main()
{
int n;
fstream fin("buline.in", fstream::in);
fstream fout("buline.out", fstream::out);
fin >> n;
//cout << n << endl;
for (int i=1; i<=n; ++i)
{
int sgn;
fin >> vec[i] >> sgn;
vec[i] *= (sgn ? 1 : -1);
}
memcpy(vec + n + 1, vec+1, n * sizeof(long long));
/*ostream_iterator<short> itOutS(cout, " ");
copy(vec, vec + 2*n + 1, itOutS);
cout << endl << endl;*/
partial_sum(vec, vec + 2*n + 1, sums);
/*ostream_iterator<long long> itOutLL(cout, " ");
copy(sums, sums + 2*n + 1, itOutLL);
cout << endl;*/
int pos = -1;
int length = 0;
long long maxSum = numeric_limits<long long>::min();
deque<int> deq;
for (int i=1; i<2*n; ++i)
{
while (!deq.empty() && sums[deq.back()] >= sums[i-1])
{
deq.pop_back();
}
deq.push_back(i-1);
if (deq.front() < i - n)
{
deq.pop_front();
}
if (sums[i] - sums[deq.front()] > maxSum)
{
maxSum = sums[i] - sums[deq.front()];
pos = deq.front() + 1;
length = i - deq.front();
}
else if (sums[i] - sums[deq.front()] == maxSum)
{
if (pos == deq.front() + 1)
{
length = min(length, i - deq.front());
}
else if (pos > deq.front() + 1)
{
pos = deq.front() + 1;
length = i - deq.front();
}
}
}
fout << maxSum << " " << pos << " " << length << "\n";
return 0;
}