Cod sursa(job #2930374)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 28 octombrie 2022 11:52:36
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 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 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;
}