Cod sursa(job #2990259)

Utilizator mati.coldea@gmail.comMatei Coldea [email protected] Data 7 martie 2023 17:59:31
Problema Buline Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
#define INF 100000
#define INF2 10000000
int a[400005];
int main() {

	ios_base::sync_with_stdio(false);
	fin.tie(NULL);

	int n;
	fin >> n;

	for (int i = 1; i <= n; i++) {
		int act, tip;
		fin >> act >> tip;
		if (tip == 0) {
			a[i] = act * -1;
		}
		else {
			a[i] = act;
		}
	}

	for (int i = 1; i <= n; i++) {
		a[n+i] = a[i];

	}



	

	

	long long rez=-INF2;
	int strez;
	int sfrez;
	long long suma = -1;
	long long sumaact = -1;
	int stact = 0;
	int st = -1;
	int sf = 0;
	int mini = -INF;
	int stmini;
	int sfmini;
	
	for (int start = 1; start <= n ; start++) {
		suma = -1;
		sumaact = -1;
		stact = 0;
		st = -1;
		sf = 0;
		mini = -INF;
		stmini = 0;
		sfmini = 0;

		for (int i = start; i <= start + n - 1; i++) {
			if (mini < a[i]) {
				mini = a[i];
				stmini = i;
				sfmini = i;
			}
			

			if (sumaact < 0) {
				stact = i;
				sumaact = 0;
			}
			sumaact += a[i];

			if (sumaact > suma) {
				st = stact;
				sf = i;
				suma = sumaact;
			}

		}
		if (st == -1) {
			if (rez < mini) {
				rez = mini;
				strez = stmini;
				sfrez = 1;
			}
			
			//cout << mini << ' ' << stmini << ' ' << 1 << '\n';
		}
		else {
			if (rez < suma) {
				rez = suma;
				strez = st;
				sfrez = sf - st + 1;
			}
			//cout << suma << ' ' << st << ' ' << sf - st + 1 << '\n';

		}

	}

	fout << rez << ' ' << strez << ' ' << sfrez;

	

	


	fin.close();
	fout.close();
}