Pagini recente » Cod sursa (job #2126608) | Cod sursa (job #435556) | Cod sursa (job #1276023) | Cod sursa (job #364458) | Cod sursa (job #2930374)
#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,sum=0;
int sMax = v[1], pozMax = 1,lMax=1;
while (start != 2 * n)
{
sum -= v[start];
start++;
if (start > sfarsit)
{
sfarsit = start;
sum = v[sfarsit];
}
while (sfarsit - start + 1 < n && sum + v[sfarsit+1] >= v[sfarsit+1])
{
sum += v[sfarsit+1];
sfarsit++;
if (sum > sMax)
{
sMax = sum;
lMax = sfarsit - start + 1;
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 + 1;
pozMax = val;
}
}
}
if (sum > sMax)
{
sMax = sum;
lMax = sfarsit - start + 1;
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 + 1;
pozMax = val;
}
}
}
fprintf(fout, "%d %d %d", sMax,pozMax, lMax);
return 0;
}