Pagini recente » Cod sursa (job #2869093) | Cod sursa (job #38015) | Cod sursa (job #803917) | Cod sursa (job #2550675) | Cod sursa (job #2961742)
#include <iostream>
#include <fstream>
#include <deque>
#include <climits>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
constexpr size_t LIM = 200005;
int N, i, a, b, arr[LIM], sum;
int max_sum, start, finish;
int main() {
max_sum = INT_MIN;
fin >> N;
for (i = 0; i < N; ++i) {
fin >> a >> b;
if (b == 0) arr[i] = -a;
else arr[i] = a;
}
deque<pair<int, int>> deq;
for (i = 0; i < N - 1; ++i) {
sum += arr[i];
while (!deq.empty() && sum < deq.back().second)
deq.pop_back();
deq.emplace_back(i, sum);
}
for (int j = 0; j < N; ++j, ++i) {
if (deq.front().first == i - N)
deq.pop_front();
sum += arr[i % N];
const int min_sum = deq.front().second;
if (sum - min_sum > max_sum) {
max_sum = sum - min_sum;
start = (deq.front().first + 1) % N;
finish = i % N;
}
while (!deq.empty() && sum < deq.back().second)
deq.pop_back();
deq.emplace_back(i, sum);
}
int len = finish - start + 1;
if (len <= 0) len += N;
fout << max_sum << ' ' << start + 1 << ' ' << len;
fin.close();
fout.close();
return 0;
}