Pagini recente » Cod sursa (job #415523) | Cod sursa (job #312409) | Cod sursa (job #307343) | Cod sursa (job #105280) | Cod sursa (job #766019)
Cod sursa(job #766019)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
#define nmax 200005
#define inf (1<<30)
ifstream f("buline.in");
ofstream g("buline.out");
int a[2*nmax], n;
deque<int> dq;
void citeste(){
f >> n;
for(int i=1; i<=n; i++){
int x, tip;
f >> x >> tip;
if (tip == 0) a[i] = -x;
else a[i] = x;
}
for(int j=1; j<=n; j++) a[j+n]=a[j];
}
void rezolva(){
int sum = 0, rez=-inf, st=0, dr=0;
for(int i=1; i<=2*n; i++){
if (sum + a[i] > a[i]){
if (i-dq.front()+1 <= n){
dq.push_back(i);
sum += a[i];
if (sum > rez){
rez = sum;
st = dq.front();
dr = i;
}
}else{
if (sum > rez){
rez = sum;
st = dq.front();
dr = i-1;
}
sum -= a[dq.front()];
dq.pop_front();
if (sum > rez){
rez = sum;
st = dq.front();
dr = i-1;
}
dq.push_back(i);
sum += a[i];
if (sum > rez){
rez = sum;
st = dq.front();
dr = i;
}
}
}else{
if (sum > rez){
rez = sum;
st = dq.front();
dr = i-1;
}
dq.clear();
sum = a[i];
dq.push_back(i);
if(sum > rez){
rez = sum;
st = dq.front();
dr = i;
}
}
}
g << rez << " " << st << " " << dr-st+1 << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
}