Pagini recente » Cod sursa (job #695714) | Cod sursa (job #1596976) | Cod sursa (job #872556) | Diferente pentru home intre reviziile 591 si 590 | Cod sursa (job #763952)
Cod sursa(job #763952)
#include <stdio.h>
#include <limits>
using namespace std;
int maxim_3(int a, int b, int c) {
int max = a;
if (b > max) {
max = b;
}
if (c > max) {
max = c;
}
return max;
}
int calc_start(int a, int b, int c, int poz_a, int poz_b, int poz_c) {
int max, max_poz;
max = a; max_poz = poz_a;
if (b > max) {
max = b;
max_poz = poz_b;
}
if (c > max) {
max = c;
max_poz = poz_c;
}
return max_poz;
}
int main()
{
FILE* f = fopen("secv2.in", "r");
FILE* g = fopen("secv2.out", "w");
short int v[50000];
int sum[50000];
int max[50000];
int max_k[50000];
int start[50000];
int n, k;
fscanf(f, "%d", &n);
fscanf(f, "%d", &k);
int maxx, p1, p1_temp, p2;
for (int i = 0; i < n; i++) {
fscanf(f, "%hd", &v[i]);
if (i > 0) {
sum[i] = sum[i-1] + v[i];
} else {
sum[i] = v[i];
}
}
maxx = -std::numeric_limits<int>::max();
max[0] = v[0] > 0 ? v[0] : 0;
start[0] = v[0] > 0 ? 0 : 1;
for (int i = 1; i < n; i++) {
max[i] = maxim_3(0, v[i], v[i] + max[i-1]);
start[i] = calc_start(0, v[i], v[i] + max[i-1], i+1, i, start[i-1]);
if (i >= k) {
max_k[i] = sum[i] - sum[i-k] + max[i-k];
p1_temp = start[i-k];
if (max_k[i] > maxx) {
maxx = max_k[i];
p1 = p1_temp;
p2 = i;
}
}
}
fprintf(g, "%d %d %d", p1 + 1, p2 + 1, maxx);
fclose(f);
fclose(g);
return 0;
}