Pagini recente » Cod sursa (job #2946189) | Cod sursa (job #1362987) | Cod sursa (job #196754) | Cod sursa (job #744670) | Cod sursa (job #3264043)
#include <bits/stdc++.h>
using namespace std;
/**
dp[i] - suma maxima a unei secvente 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;
cin >> n;
for (int i = 1; i <= n; ++i)
{
int x, c;
cin >> x >> c;
if (c == 0)
a[i] = -x;
else
a[i] = x;
}
for (int i = 1; i <= n; ++i)
a[n+i] = a[i];
int ans = 0, ans_left, ans_right, st = 1, maxim = INT_MIN;
dp[1] = a[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 (maxim > ans)
{
maxim = ans;
ans_left = st, ans_right = i;
}
}
for (int i = 1; i <= n; ++i)
dp[i] = 0;
for (int i = 1; i <= n-1; ++i)
{
int maxim = INT_MIN, st = i, left, right;
dp[i] = a[i];
for (int j = i+1; j <= n+i; ++j)
{
if (dp[j-1] + a[j] >= a[j])
dp[j] = dp[j-1] + a[j];
else
{
st = j;
dp[j] = a[j];
}
if (dp[j] > maxim)
{
left = st, right = j;
maxim = dp[j];
}
}
if (maxim > ans)
{
ans = maxim;
ans_left = left, ans_right = right;
}
}
cout << ans << " " << ans_left << " " << ans_right - ans_left + 1;
return 0;
}