Cod sursa(job #1152905)

Utilizator harababurelPuscas Sergiu harababurel Data 25 martie 2014 08:51:01
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <iostream>
#include <fstream>
#define nmax 50005
#define inf (1<<30)
using namespace std;

int v[nmax], sum[nmax], dp[nmax], ssm[nmax];
int n, k, sol = -inf, lo, hi, x;

int main() {
	ifstream f("secv2.in");
	ofstream g("secv2.out");

	f>>n>>k;
	for(int i=1; i<=n; i++) {
		f>>v[i];
		sum[i] = sum[i-1] + v[i];

		ssm[i] = max(ssm[i-1] + v[i], v[i]);
		ssm[i] = max(ssm[i], 0);
	}

	for(int i=k; i<=n; i++) {
		dp[i] = max(ssm[i-k] + sum[i] - sum[i-k], sum[i] - sum[i-k]);
		if(dp[i] > sol) sol = dp[i], hi = i;
	}

	//for(int i=1; i<=n; i++) cout<<dp[i]<<" "; cout<<"\n\n";

	lo = hi;
	x = sol;
	while(x) x -= v[lo--]; 

	g<<lo+1<<" "<<hi<<" "<<sol<<"\n";
	return 0;
}