Pagini recente » Cod sursa (job #2315349) | Cod sursa (job #144273) | Cod sursa (job #2207489) | Cod sursa (job #1770600) | Cod sursa (job #799966)
Cod sursa(job #799966)
#include<fstream>
using namespace std;
int v[100000],d[100000],i,j,n,a,p,nr, smax, s1min, pmax, lmax, lung, pfmax, lc, pc, lungmax, S;
int main()
{
ifstream f("buline.in");
ofstream g("buline.out");
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i]>>a;
if(a==0) {
v[i]=-v[i];
}
S += v[i];
}
d[1]=v[1];
smax = d[1];
pmax = 1;
lmax = 1;
for (i=2;i<=n;i++){
if (v[i] > d[i-1] + v[i]) {
d[i] = v[i];
pc = i;
lc = 1;
} else {
d[i] = d[i-1] + v[i];
lc ++;
}
if (d[i] > smax) {
smax = d[i];
pmax = pc;
lmax = lc;
}
}
//calculez subsecventa de suma minim care se termina cat mai devreme
d[1] = v[1];
s1min = d[1];
for(i=2;i<=n;i++) {
if (d[i-1] + v[i] < v[i]) {
d[i] = d[i-1] + v[i];
lung ++;
} else {
d[i] = v[i];
lung = 1;
}
if (d[i] <= s1min) {
s1min = d[i];
pfmax = i;
lungmax = lung;
}
}
s1min = S - s1min;
if (s1min > smax) {
smax = s1min;
pmax = pfmax+1;
lmax = n-lungmax;
}
g<<smax<<" "<<pmax<<" "<<lmax;
return 0;
}