Pagini recente » Cod sursa (job #2315318) | Cod sursa (job #66305) | Cod sursa (job #1015085) | Cod sursa (job #1149788) | Cod sursa (job #2930387)
#include <cstdio>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>
#define NMAX 200003
#define MOD 1000000007
using namespace std;
int n;
int v[NMAX * 2];
FILE* fin, * fout;
int main()
{
fin = fopen("buline.in", "r");
fout = fopen("buline.out", "w");
fscanf(fin,"%d", &n);
for (int i = 1; i <= n; i++)
{
int x, sgn;
fscanf(fin, "%d %d", &x, &sgn);
if (sgn == 0)
{
v[i] = -x;
v[i + n] = -x;
}
else {
v[i] = x;
v[i + n] = x;
}
}
int start = 0,sfarsit=0;
long long int sum=0,sMax=v[1];
int pozMax = 1,lMax=1;
while (start != 2 * n)
{
sum -= v[start];
start++;
if (start >= sfarsit)
{
sum = v[start];
sfarsit = start + 1;
}
//fac subsecv de suma maxima
while (sfarsit <= 2 * n && sfarsit - start < n && sum + v[sfarsit] >= v[sfarsit])
{
sum += v[sfarsit];
sfarsit++;
if (sum > sMax)
{
sMax = sum;
lMax = sfarsit - start;
pozMax = start;
if (pozMax > n)
{
pozMax -= n;
}
}
else if (sum == sMax)
{
//trebuie sa iau dupa pozMinim
int val = start;
if (val > n)
{
val -= n;
}
if (val < pozMax)
{
lMax = sfarsit - start;
pozMax = val;
}
else if (val == pozMax)
{
lMax = min(sfarsit - start, lMax);
}
}
}
if (sum > sMax)
{
sMax = sum;
lMax = sfarsit - start;
pozMax = start;
if (pozMax > n)
{
pozMax -= n;
}
}
else if (sum == sMax)
{
//trebuie sa iau dupa pozMinim
int val = start;
if (val > n)
{
val -= n;
}
if (val < pozMax)
{
lMax = sfarsit - start;
pozMax = val;
}
else if (val == pozMax)
{
lMax = min(sfarsit - start, lMax);
}
}
}
fprintf(fout, "%lld %d %d", sMax,pozMax, lMax);
return 0;
}