Pagini recente » Cod sursa (job #1223670) | Cod sursa (job #2255738) | Cod sursa (job #2063646) | Cod sursa (job #1462) | Cod sursa (job #3264633)
#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;
}