Pagini recente » Cod sursa (job #2779777) | Rating Sut Oana (oanantonia) | Cod sursa (job #3276462) | Cod sursa (job #1592101) | Cod sursa (job #2118336)
#include <fstream>
using namespace std;
ifstream cin ("buline.in");
ofstream cout ("buline.out");
const int MAX_N = 400000;
int Dq[1 + MAX_N];
int Sum[1 + MAX_N];
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
int X;
bool tip;
cin >> X >> tip;
if(tip == 0)
X = -X;
Sum[i] = Sum[i + n] = X;
}
for(int i = 1; i <= 2 * n; i++)
Sum[i] += Sum[i - 1];
int Front = 1, Back = 0, sumMax = 0, l, r;
for(int i = 1; i <= 2 * n; i++) {
while(Front <= Back && Sum[i] <= Sum[Dq[Back]])
Back--;
Dq[++Back] = i;
while(Front <= Back && i - Dq[Front] > n)
Front++;
if(sumMax < Sum[i] - Sum[Dq[Front]]) {
sumMax = Sum[i] - Sum[Dq[Front]];
l = Dq[Front] + 1;
r = i;
}
}
cout << sumMax << " " << l << " " << r - l + 1;
return 0;
}