Pagini recente » Cod sursa (job #1721093) | Cod sursa (job #405139) | Cod sursa (job #1465694) | Cod sursa (job #834671) | Cod sursa (job #267851)
Cod sursa(job #267851)
#include <stdio.h>
#define DIM 50002
#define INF 1250000002
int v[DIM],S[DIM],MIN[DIM],P[DIM];
long n,k,i,begin,end,ibegin,iend;
long long max;
//S[i] = vectorul de sume partiale
//MIN[i] = cel mai mic S de la 1 la i
//P[i] = pozitia pe care e MIN[i]
int main(){
FILE *f = fopen("secv2.in", "r");
FILE *g = fopen("secv2.out", "w");
fscanf(f,"%ld%ld",&n,&k);
for (i=1; i<=n; i++)
fscanf(f,"%d",&v[i]);
S[1] = v[1];
MIN[1] = S[1];
P[1] = 1;
max = -INF;
for (i=2; i<=n; i++) {
S[i] = S[i-1] + v[i];
if (S[i] < MIN[i-1]) {
MIN[i] = S[i];
P[i] = i;
}
else {
MIN[i] = MIN[i-1];
P[i] = P[i-1];
}
if (i >= k) {
if (S[i]-MIN[i-k] > max) {
max = S[i]-MIN[i-k];
begin = P[i-k]+1;
end = i;
}
if (S[i] > max) {
max = S[i];
begin = 1;
end = i;
}
}
}
fprintf(g,"%ld %ld %lld\n",begin,end,max);
fclose(f);
fclose(g);
return 0;
}