Pagini recente » Cod sursa (job #337303) | Cod sursa (job #300071) | Cod sursa (job #1092736) | Cod sursa (job #1722638) | Cod sursa (job #30198)
Cod sursa(job #30198)
#include <cstdio>
#include <algorithm>
using namespace std;
#define mp make_pair
#define x first
#define y second.first
#define z second.second
#define inf (int)(2*1e10)
#define Nmax 200005
int n;
long long v[Nmax];
long long Q[2*Nmax], E[2*Nmax], qe, qb;
pair< int, pair<int, int> > best;
void readdata()
{
freopen("buline.in", "r", stdin);
freopen("buline.out", "w", stdout);
int i, val, semn;
scanf("%d", &n);
for (i = 1; i <= n; ++i)
{
scanf("%d %d", &val, &semn);
v[i] = !semn ? -val : val;
}
}
void solve()
{
int i;
for (i = 1; i <= n; ++i)
v[n+i] = v[i];
for (i = 2; i <= 2*n; ++i)
v[i] += v[i-1];
best.x = -inf;
Q[qe = qb = 1] = E[qb] = 0;
for (i = 1; i <= 2*n; ++i)
{
if (E[qb] < i-n) ++qb;
if (v[i]-Q[qb] > best.x)
{
best.x = v[i]-Q[qb];
best.y = E[qb]+1 > n ? E[qb]+1-n : E[qb]+1;
best.z = i-E[qb];
}
else
if (v[i]-qb == best.x && (E[qb]+1 > n ? E[qb]+1-n : E[qb]+1) < best.y)
{
best.y = E[qb]+1 > n ? E[qb]+1-n : E[qb]+1;
best.z = i-E[qb];
}
while (qe >= qb && v[i] < Q[qe]) --qe;
Q[++qe] = v[i], E[qe] = i;
}
}
void writedata()
{
printf("%d %d %d\n", best.x, best.y, best.z);
}
int main()
{
readdata();
solve();
writedata();
return 0;
}