Pagini recente » Cod sursa (job #781134) | Cod sursa (job #3192466) | Cod sursa (job #2487898) | Cod sursa (job #1519495) | Cod sursa (job #2293845)
#include <fstream>
#include <vector>
#include <deque>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
const int Inf = INT_MAX;
class DequeItm {
public:
int sum, idx;
};
int main() {
int N;
fin >> N;
vector <int> Arr(2 * N + 1);
for (int idx = 1; idx <= N; ++idx) {
int val;
bool type;
fin >> val >> type;
if (type == 0)
Arr[idx] = Arr[idx + N] = -val;
else
Arr[idx] = Arr[idx + N] = val;
}
int S = -Inf, P = 0, L = 0;
deque <DequeItm> Deque;
Deque.push_back({ 0, 0 });
int partSum = 0;
for (int idx = 1; idx <= 2 * N; ++idx) {
while (!Deque.empty() && Deque.front().idx < idx - N + 1)
Deque.pop_front();
partSum += Arr[idx];
int sum = partSum - Deque.front().sum;
if (sum > S) {
S = sum;
P = Deque.front().idx;
L = idx - Deque.front().idx;
}
while (!Deque.empty() && partSum < Deque.back().sum)
Deque.pop_back();
Deque.push_back({partSum, idx});
}
fout << S << ' ' << P + 1 << ' ' << L;
}