Pagini recente » Cod sursa (job #1991936) | Cod sursa (job #455872) | Cod sursa (job #1947170) | Cod sursa (job #372918) | Cod sursa (job #2200670)
#include <cstdio>
#include <deque>
#include <cstring>
using namespace std;
char s[8000005];
int v[500005];
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int n,k;
scanf("%d%d\n",&n,&k);
long long sum=0;
int min1=-99999999,poz1=0;
deque<int>d;
deque<int>poz;
gets(s);
int l=strlen(s);
int semn=1,cnt=1;
for(register int i=0;i<l;i++)
{#include <cstdio>
#include <deque>
using namespace std;
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int n,k;
scanf("%d%d",&n,&k);
long long sum=0;
deque<int>d;
deque<int>poz;
for(register int i=1;i<=n;i++)
{
int nr;
scanf("%d",&nr);
if(i<k)
{
while(!d.empty())
{
if(d.back()>=nr)d.pop_back(),poz.pop_back();
else
break;
}
d.push_back(nr);
poz.push_back(i);
continue;
}
if(i>=k)
{
while(!d.empty())
{
if(d.back()>=nr)d.pop_back(),poz.pop_back();
else
break;
}
d.push_back(nr);
poz.push_back(i);
sum+=d.front();
if(poz.front()==(i-k+1))
d.pop_front(),poz.pop_front();
}
}
printf("%lld",sum);
return 0;
}
if(s[i]==' ')continue;
if(s[i]=='-')
{
semn=-1;
continue;
}
int nr1=0;
while(s[i]>='0'&&s[i]<='9')
{
nr1=nr1*10+s[i]-'0';
i++;
}
v[cnt]=nr1*semn;
cnt++;
semn=1;
}
for(register int i=1;i<=n;i++)
{
int nr;
nr=v[i];
if(i<k)
{
while(!d.empty())
{
if(d.back()>= nr)d.pop_back(),poz.pop_back();
else
break;
}
d.push_back(nr);
poz.push_back(i);
continue;
}
if(i>=k)
{
while(!d.empty())
{
if(d.back()>= nr)d.pop_back(),poz.pop_back();
else
break;
}
d.push_back(nr);
poz.push_back(i);
if(d.front()>min1)
{
min1=d.front();
poz1=i-k+1;
}
if(poz.front()==(i-k+1))
d.pop_front(),poz.pop_front();
}
}
printf("%d %d %d\n",poz1,poz1+k-1,min1);
return 0;
}