Pagini recente » Cod sursa (job #2006842) | Cod sursa (job #1573380) | Cod sursa (job #2571128) | Cod sursa (job #142353) | Cod sursa (job #1307366)
#include <cstdio>
#include <fstream>
#define nmax 200005
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,v[nmax];
int maxuc=-(1<<30),maxfin;
int s[nmax],nr[nmax],nr1,t[nmax];
int pot1,pot2,sol=(-1<<30),poz,lg,sum;
int main() {
int i,j;
f>>n;
for (i=1;i<=n;i++) {
f>>v[i]>>j;
if (j==0) v[i]=-v[i];
}
//precalculez de la inceput
for (i=1;i<=n;i++)
s[i]=s[i-1]+v[i];
for (i=1;i<=n;i++){
if (s[i]>s[i-1]) nr[i]=i;
else nr[i]=nr[i-1];
s[i]=max(s[i-1],s[i]);
}
//precalculez catre final
for (i=1;i<=n;i++) t[i]=t[i-1]+v[i];
//gasesc solutiile
if (t[n]>maxuc){
maxuc=t[n];
nr1=n;
}
for (i=n;i>=1;i--) {
pot1=t[n]-t[i-1]+s[i-1];
pot2=maxuc-t[i-1];
if (pot2>=sol) {
sol=pot2;
poz=i;
lg=nr1-i+1;
}
if (pot1>=sol) {
sol=pot1;
poz=i;
lg=n-i+1+nr[i-1];
}
if (t[i-1]>maxuc) {
maxuc=t[i-1];
nr1=i-1;
}
}
g<<sol<<' '<<poz<<' '<<lg;
return 0;
}