Pagini recente » Cod sursa (job #822179) | Cod sursa (job #1564451) | Cod sursa (job #1917901) | Cod sursa (job #3135986) | Cod sursa (job #2930400)
#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;// imi iau o secventa aici de n elemente care are suma maxima
coada.push_back(0);
int sMax = sume[0], pozMax = 1, lMax = 1;
for (int i = 1; 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()+1 > n)
{
coada.pop_front();
}
//verific daca am suma din secventa [coada.front, i] maxima
if (sume[i] - sume[coada.front()-1] > sMax)
{
sMax = sume[i] - sume[coada.front()-1];
pozMax = coada.front();
lMax = i - coada.front() + 1;
}
//daca am sume[i]<sume[coada.back()] inseamna ca am subsecventa de sum maxima mai mare in secventa, deci scoate celelalte secvente
while (!coada.empty() && sume[coada.back()-1] > sume[i])
{
coada.pop_back();
}
coada.push_back(i);//pun elementul i
}
fprintf(fout, "%d %d %d", sMax,pozMax, lMax);
return 0;
}