Pagini recente » Cod sursa (job #2544767) | Cod sursa (job #238234) | Cod sursa (job #647001) | Cod sursa (job #375793) | Cod sursa (job #65422)
Cod sursa(job #65422)
#include <stdio.h>
#include <assert.h>
/*
* I suck at naming variables.
*/
enum { maxn = 50001 };
int n, minlen;
int p[maxn];
int best_start, best_end, best;
//any length
int best_ending_at[maxn]; //value
int start_best_ending_at[maxn]; //start pos
//minlen
int sum_ending_at[maxn];
//minlen or more
int ending_at[maxn]; //value
int start_ending_at[maxn]; //start pos
//any length
void calc_best()
{
best_ending_at[0] = p[0];
start_best_ending_at[0] = 0;
for(int end = 1; end < n; end++)
{
best_ending_at[end] = p[end];
start_best_ending_at[end] = end;
if(best_ending_at[end - 1] > 0) //longer better?
{
best_ending_at[end] += best_ending_at[end - 1];
start_best_ending_at[end] = start_best_ending_at[end - 1];
}
}
}
void go()
{
int end, i;
calc_best();
for(i = 0; i < minlen; i++)
sum_ending_at[minlen - 1] += p[i];
ending_at[minlen - 1] = sum_ending_at[minlen - 1];
start_ending_at[minlen - 1] = 0;
best = ending_at[minlen - 1];
best_start = start_ending_at[minlen - 1];
best_end = minlen - 1;
for(end = minlen; end < n; end++)
{
sum_ending_at[end] = sum_ending_at[end - 1] - p[end - minlen] + p[end];
ending_at[end] = sum_ending_at[end];
int start = end - minlen + 1;
start_ending_at[end] = start;
if(best_ending_at[start - 1] > 0) //longer better?
{
ending_at[end] += best_ending_at[start - 1];
start_ending_at[end] = start_best_ending_at[start - 1];
}
if(ending_at[end] > best)
{
best = ending_at[end];
best_start = start_ending_at[end];
best_end = end;
}
}
}
int main()
{
int i;
FILE *f = fopen("secv2.in", "r");
if(!f) return 1;
fscanf(f, "%d%d", &n, &minlen);
for(i = 0; i < n; i++)
fscanf(f, "%d", &p[i]);
fclose(f);
f = fopen("secv2.out", "w");
if(!f) return 1;
go();
fprintf(f, "%d %d %d\n", best_start + 1, best_end + 1, best);
fclose(f);
return 0;
}