Cod sursa(job #87623)

Utilizator gigi_becaliGigi Becali gigi_becali Data 27 septembrie 2007 22:03:42
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
using namespace std;
#include <map>
#include <cstdio>
#define maxn 50001
map<int, int> a;

int n, K, x[maxn];
int s[maxn];

void read()
{
	freopen("secv2.in","r",stdin);
	scanf("%d %d\n", &n, &K);
	int i;
	for(i=1;i<=n;++i)scanf("%d ", x+i);
}

void solve()
{
	int i;
	s[1]=x[1];
	for(i=2;i<=n;++i) s[i]=s[i-1]+x[i];

a[0]=0;	
	a[s[1]]=1;
	map<int, int>::iterator it;
	for(i=2;i<K;++i)
		if(!a[s[i]]) a[s[i]]=i;
	int p=0, q=0,max=-0x3f3f3f3f;
	for(i=K;i<=n;++i)
	{
		int ok=0;
		for(it=a.begin();it!=a.end();++it)
			if(i-it->second>=K) {ok=1;break;}
		if(ok && s[i]-s[it->second]>max)
		{
			p=it->second;
			q=i;
			max=s[i]-s[it->second];
		}
		if(!a[s[i]]) a[s[i]]=i;
	}
	freopen("secv2.out","w",stdout);
	printf("%d %d %d\n", p+1, q, max);
			
	
}

int main()
{
	read();
	solve();
	return 0;
}