Pagini recente » Cod sursa (job #141450) | Cod sursa (job #936497) | Cod sursa (job #2128240) | Cod sursa (job #2420429) | Cod sursa (job #2930401)
#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 sume[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);
int val = 0;
if (sgn == 0)
{
val = -x;
}
else {
val = x;
}
sume[i] = val;
sume[i + n] = val;
}
deque<int>coada;//secvente de lungime maxima de maxim lungime n
coada.push_back(1);
int sMax = sume[1], pozMax = 1, lMax = 1;
for (int i = 2; i <= 2 * n; i++)
{
sume[i] += sume[i - 1];
//scot din deque toate elementele care se repeta in ciclu
while (!coada.empty() && i-coada.front() > n)
{
coada.pop_front();
}
//verific daca am suma din secventa (coada.front, i] maxima
if (sume[i] - sume[coada.front()] > sMax)
{
sMax = sume[i] - sume[coada.front()];
pozMax = coada.front() + 1;
lMax = i - coada.front();
}
//daca am sume[i]<sume[coada.back()] inseamna ca am subsecventa de sum maxima mai mare in secventa, deci sume[i] imi scoate elementele pentru ca deja le calculasem suma inainte
while (!coada.empty() && sume[coada.back()] > sume[i])
{
coada.pop_back();
}
coada.push_back(i);
}
fprintf(fout, "%d %d %d", sMax,pozMax, lMax);
return 0;
}