Cod sursa(job #3264633)

Utilizator luc3lexa_Alexandrescu Luca luc3lexa_ Data 22 decembrie 2024 20:24:37
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");

const int nmax = 2e5+10;
const int inf = 1e9;

vector<int> values(nmax,0);
vector<pair<int,int>> dp(nmax,{-inf,inf});
int n,aux,value,ans_1,ans_2,total_sum;
int first_index,first_length,second_index,second_length;
int ans_1_length,ans_2_length;

void read_input(){
	fin >> n;
	for(int i = 1; i <=n; i++){
		fin >> value >> aux;
		values[i] = (aux == 0 ? -value : value);
		total_sum += values[i];
	}
}

void solve(){
	ans_1 = -inf,ans_2 = inf;
	dp[1].first = values[1];
	dp[1].second = values[1];
	for(int i = 2; i <=n; i++){
		if(dp[i-1].first + values[i] > values[i]){
			dp[i].first = dp[i-1].first + values[i];
			first_length++;
		}else{
			dp[i].first = values[i];
			first_length = 1;
		}
		if(ans_1 < dp[i].first){
			first_index = i - first_length + 1;
			ans_1_length = first_length;
			ans_1 = dp[i].first;
		}
		
		if(dp[i-1].second + values[i] < values[i]){
			dp[i].second = dp[i-1].second + values[i];
			second_length++;
		}else{
			dp[i].second = values[i];
			second_length = 1;
		}
		if(ans_2 > dp[i].second){
			second_index = i - second_length + 1;
			ans_2_length = second_length;
			ans_2 = dp[i].second;
		}
	};
	
}

int main(){
	read_input();
	solve();
	if(ans_1 > total_sum - ans_2){
		fout << ans_1 << " " << first_index << " " << ans_1_length;
	}else{
		fout << total_sum - ans_2 << " " << second_index + ans_2_length << " " << n-ans_2_length;
	}
	return 0;
}