Pagini recente » preONI 2008 - Organizatori | Cod sursa (job #1719481) | Cod sursa (job #3210856) | Cod sursa (job #2921350) | Cod sursa (job #218949)
Cod sursa(job #218949)
#include <stdio.h>
#define DIM 50002
long long A[DIM],K[DIM],V[DIM],L[DIM];
long long n,k,i,max,s,pMax;
int main(){
FILE *f = fopen("secv2.in","r");
fscanf(f,"%lld %lld",&n,&k);
for (i=1;i<=n;i++) {
fscanf(f,"%lld",&V[i]);
if (i<=k)
s+=V[i];
if (i==k){
A[i] = s;
K[i] = s;
}
if (i>k) {
K[i] = K[i-1]+V[i]-V[i-k];
if ((A[i-1]+V[i]>=K[i]) && (A[i-1]+V[i]>=A[i-1]+V[i]-V[i-1-L[i-1]+1])){
A[i] = A[i-1]+V[i];
L[i] = L[i-1]+1;
} else if ((K[i]>=A[i-1]+V[i]) && (K[i]>=A[i-1]+V[i]-V[i-1-L[i-1]+1])){
A[i] = K[i];
L[i] = k;
} else if ((A[i-1]+V[i]-V[i-1-L[i-1]+1]>=A[i-1]+V[i]) && (A[i-1]+V[i]-V[i-1-L[i-1]+1]>A[i-1]+V[i])){
A[i] = A[i-1]+V[i]-V[i-1-L[i-1]+1];
L[i] = L[i-1];
}
}
}
fclose(f);
max = A[k];
pMax = k;
for (i=k+1;i<=n;i++)
if (A[i]>max){
max = A[i];
pMax = i;
}
FILE *g = fopen("secv2.out","w");
fprintf(g,"%lld %lld %lld",pMax-L[pMax]+1,pMax,max);
fclose(g);
return 0;
}