Salut, am si eu o problema de pe Codeforces la care iau wrong answer:
http://codeforces.com/gym/100513/problem/FStiu ca am postat intr-o sectiune gresita, dar nu am gasit niciuna pentru Codeforces.
Acum, problema mi se pare destul de banala, daca am inteles bine enuntul.
Algoritmul face asa:
1) daca 2*k>n afisam suma elementelor.
2) altfel, calculez cea mai mare suma de k elemente consecutive, o elimin, si apoi o calculez pe a doua cea mai mare din ce a ramas.
Sursa mea:
//horatiu11
# include <iostream>
# include <fstream>
# define nmax 2000001
using namespace std;
ifstream f("F.in");
ofstream g("F.out");
int n,k,a[nmax],p,q,nou[nmax],m;
long long s1,s2,sp;
int main()
{
int i;
f>>n>>k;
for(i=1;i<=n;++i)
f>>a[i];
if(2*k>n)
{
for(i=1;i<=n;++i)
s1+=a[i];
g<<s1<<'\n';
}
else
{
sp=0;
for(i=1;i<=k;++i)
sp+=a[i];
p=1;q=k;s1=sp;
for(i=k+1;i<=n;++i)
{
sp-=a[i-k];
sp+=a[i];
if(s1<sp)s1=sp,p=i-k+1,q=i;
}
for(i=1;i<p;++i)
nou[++m]=a[i];
for(i=q+1;i<=n;++i)
nou[++m]=a[i];
sp=0;
for(i=1;i<=k;++i)
sp+=nou[i];
s2=sp;
for(i=k+1;i<=m;++i)
{
sp-=nou[i-k];
sp+=nou[i];
if(s2<sp)s2=sp;
}
g<<s1+s2<<'\n';
}
return 0;
}