Cod sursa(job #763952)

Utilizator mi5humihai draghici mi5hu Data 3 iulie 2012 16:36:12
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#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;
}