Pagini recente » Cod sursa (job #330900) | Cod sursa (job #1114185) | Cod sursa (job #2330092) | Cod sursa (job #2406903) | Cod sursa (job #1829209)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int n, best_sum, best_sum_pos, best_sum_lg, SUM[400010];
deque < int > DQ;
int main()
{
fin >> n;
for (int aa, av, i = 1; i <= n; i ++)
{
fin >> av >> aa;
if (!aa) av = -av;
SUM[i] = SUM[i - 1] + av;
SUM[i + n] = av;
}
for (int i = n + 1; i <= n * 2; i ++) SUM[i] += SUM[i - 1];
best_sum = SUM[1];
DQ.push_back(1);
for (int i = 2; i <= n * 2; i ++)
{
if (i - DQ.front() > n) DQ.pop_front();
if (SUM[i] - SUM[DQ.front()] > best_sum)
{
best_sum = SUM[i] - SUM[DQ.front()];
best_sum_pos = DQ.front() + 1;
best_sum_lg = i - DQ.front();
}
while (!DQ.empty() && SUM[i] < SUM[DQ.back()]) DQ.pop_back();
DQ.push_back(i);
}
fout << best_sum << ' ' << best_sum_pos<< ' ' << best_sum_lg << '\n';
fout.close();
return 0;
}