Pagini recente » Cod sursa (job #978546) | Cod sursa (job #380221) | Cod sursa (job #3267847) | Cod sursa (job #2121939) | Cod sursa (job #3264063)
#include <bits/stdc++.h>
using namespace std;
/**
dp[i] - secventa de suma minima care se termina in i
*/
const int MAX = 6000005;
int a[MAX], dp[MAX];
int main()
{
ifstream cin("buline.in");
ofstream cout("buline.out");
int n, total = 0, st = 1, raspSt, raspLen, len, maxim = INT_MIN;
cin >> n;
for (int i = 1; i <= n; ++i)
{
int x, c;
cin >> x >> c;
a[i] = (c == 0) ? -x : x;
total += a[i];
}
dp[1] = a[1], len = 1;
for (int i = 2; i <= n; ++i)
{
if (dp[i-1] + a[i] > a[i])
{
dp[i] = dp[i-1] + a[i];
++len;
}
else
{
st = i;
len = 1;
dp[i] = a[i];
}
if (dp[i] > maxim)
{
maxim = dp[i];
raspSt = st;
raspLen = len;
}
}
for (int i = 1; i <= n; ++i)
dp[i] = 0;
int minim = INT_MAX, raspSt2, raspLen2;
dp[1] = a[1], st = 1, len = 1;
for (int i = 2; i <= n; ++i)
{
if (dp[i-1] + a[i] < a[i])
dp[i] = dp[i-1] + a[i];
else
{
st = i;
dp[i] = a[i];
}
if (minim > dp[i])
{
minim = dp[i];
raspSt2 = i+1;
raspLen2 = st - 1;
}
}
if (maxim > total - minim)
cout << maxim << " " << raspSt << " " << raspLen;
else
cout << total - minim << " " << raspSt2 << " " << (n+raspLen2) - raspSt2 + 1;
return 0;
}