Cod sursa(job #2930401)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 28 octombrie 2022 12:59:17
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#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;
}