Pagini recente » Cod sursa (job #3210557) | Cod sursa (job #139016) | Cod sursa (job #934361) | Cod sursa (job #2555586) | Cod sursa (job #1450582)
#include <cstdio>
#include <vector>
#include <deque>
using namespace std;
int n , i , bulina , ans , start , finish;
vector < int > a , dp;
deque < int > D;
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d", &n);
a = vector < int > (n + 1);
for (i = 1; i <= n; ++i)
{
scanf("%d %d", &a[i], &bulina);
if (!bulina) a[i] = a[i] * (-1);
}
for (i = 1; i < n; ++i)
a.push_back(a[i]);
dp = vector < int > (n << 1);
for (i = 1; i < (n << 1); ++i)
dp[i] = dp[i-1] + a[i];
ans = a[1]; start = 1; finish = 1;
for (D.push_back(1), i = 2; i < (n << 1); ++i)
{
if (!D.empty() && D.front() + n == i)
D.pop_front();
while (!D.empty() && dp[D.back()] > dp[i])
D.pop_back();
if (dp[i] - dp[D.front()] > ans)
{
ans = dp[i] - dp[D.front()];
start = D.front() + 1;
finish = i;
}
D.push_back(i);
}
printf("%d %d %d\n", ans , start , finish - start + 1);
return 0;
}