Pagini recente » Cod sursa (job #590813) | Cod sursa (job #1296342) | Cod sursa (job #627441) | Cod sursa (job #2956906) | Cod sursa (job #766024)
Cod sursa(job #766024)
#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, s[2*nmax];
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(){
for(int i=1; i<=2*n; i++) s[i] = s[i-1] + a[i];
int rez = -inf, st = 0, dr = 0;
for(int i=1; i<=2*n; i++){
while(dq.size() && i-dq.front()+1 > n) dq.pop_front();//scot secv de lungime mai mare ca si n
while(dq.size() && s[i] < s[dq.back()]) dq.pop_back();
dq.push_back(i);
if (rez < s[i]-s[dq.front()]){
rez = s[i]-s[dq.front()];
st = dq.front()+1;
dr = i;
}
}
g << rez << " " << st << " "<< dr-st+1<<"\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
}