Pagini recente » Cod sursa (job #2535244) | Cod sursa (job #879258) | Cod sursa (job #1815658) | Cod sursa (job #1942213) | Cod sursa (job #1527282)
#include <fstream>
#include <deque>
#define NMAX 400010
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
deque <int> d;
int v[NMAX] , suma[NMAX], maxim=-100000 ,n,semn, inceput, sfarsit;
int main() {
f >> n;
int val;
for(int i = 0; i < n; i++) {
f >> val >> semn;
if(semn == 0) {
v[i] = v[i+n] = -val;
}
else {
v[i] = v[i+n] = val;
}
suma[i] = suma[i-1] + v[i];
}
for(int i = n; i < 2*n; i++) {
suma[i] = suma[i-1] + v[i];
}
for(int i = 0; i < 2*n; i++) {
while(!d.size() && suma[i] <= suma[d.back()]) {
d.pop_front();
}
d.push_back(i);
if(d.front() == i - n) {
d.pop_front();
}
if(maxim < suma[i] - suma[d.front()]) {
maxim = suma[i] - suma[d.front()];
inceput = d.front()+1;
sfarsit = i - d.front()-1;
}
}
g << maxim << " " << inceput+1 << " " << sfarsit+1;
}