Pagini recente » Cod sursa (job #1426259) | Cod sursa (job #402426) | Cod sursa (job #1169634) | Cod sursa (job #1730798) | Cod sursa (job #3287280)
#include <fstream>
using namespace std;
ifstream in("buline.in");
ofstream out("buline.out");
const int sizee = 200000;
int n, val, type, v[sizee + 2];
int totalsum;
int smax = -(1 << 30);
struct komp{ int maxi, st, dr; };
komp summax(){
komp bestt = {-(1 << 30), 0, 0};
int summy = 0, __leftt = 0;
for(int i = 1; i <= n; i++){
summy += v[i];
if(summy < 0){
summy = 0;
__leftt = i + 1;
}
if(summy > bestt.maxi){
bestt.maxi = summy;
bestt.st = __leftt;
bestt.dr = i;
}
}
return bestt;
}
int main(){
in>>n;
for(int i = 1; i <= n; i++){
in>>val>>type; val *= (type ? 1 : -1);
v[i] = val; totalsum += v[i];
}
komp p = summax();
for(int i = 1; i <= n; i++) v[i] *= (-1);
komp m = summax();
///out<<p.maxi<<" "<<p.st<<" "<<p.dr<<"\n";
///out<<m.maxi<<" "<<m.st<<" "<<m.dr<<"\n";
if(p.maxi > totalsum + m.maxi){
out<<p.maxi<<" "<<p.st<<" "<<p.dr<<"\n";
}else{
out<<totalsum + m.maxi<<" "<<((m.dr == n) ? 1 : m.dr + 1)<<" "<<n - (m.dr - m.st + 1)<<"\n";
}
return 0;
}