Cod sursa(job #2930385)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 28 octombrie 2022 12:06:30
Problema Buline Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 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 = 1;
	long long int sMax=v[1];
	int pozMax = 1,lMax=1;
	while (start != 2 * n)
	{
		//fac subsecv de suma maxima
		int sfarsit = start + 1;
		long long int sum = v[start];
		while (sfarsit <= 2 * n && sfarsit - start < n && sum + v[sfarsit] >= v[sfarsit])
		{
			sum += v[sfarsit];
			sfarsit++;
			if (sum > sMax)
			{
				sMax = sum;
				lMax = sfarsit - start;
				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;
					pozMax = val;
				}
				else if (val == pozMax)
				{
					lMax = min(sfarsit - start, lMax);
				}
			}
		}
		if (sum > sMax)
		{
			sMax = sum;
			lMax = sfarsit - start;
			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;
				pozMax = val;
			}
			else if (val == pozMax)
			{
				lMax = min(sfarsit - start, lMax);
			}
		}
		start++;
	}
	fprintf(fout, "%lld %d %d", sMax,pozMax, lMax);
	return 0;
}