Cod sursa(job #911666)

Utilizator fhandreiAndrei Hareza fhandrei Data 11 martie 2013 20:17:49
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
// Include
#include <fstream>
using namespace std;

// Definitii
#define mp make_pair
#define pii pair<int, int>
#define val first
#define id second

// Constante
const int sz = (int)5e4+1;

// Variabile
ifstream in("secv2.in");
ofstream out("secv2.out");

int num, len;

int sum[sz];

pii currentStart, currentLast;
int maxVal, maxStart, maxLast;

// Main
int main()
{
	in >> num >> len;
	for(int i=1 ; i<=num ; ++i)
		in >> sum[i], sum[i] += sum[i-1];
	
	for(int i=len ; i<=num ; ++i)
	{
		if(sum[i-len] < currentStart.val)
			currentStart = mp(sum[i-len], i-len+1);
		currentLast = mp(sum[i], i);
		if(currentLast.val - currentStart.val > maxVal)
		{
			maxVal = currentLast.val - currentStart.val;
			maxStart = currentStart.id;
			maxLast = currentLast.id;
		}
	}
	
	out << maxStart << ' ' << maxLast << ' ' << maxVal << '\n';
	
	in.close();
	out.close();
	return 0;
}