Pagini recente » Cod sursa (job #1482152) | Cod sursa (job #3295311) | Cod sursa (job #1703680) | Cod sursa (job #988563) | Cod sursa (job #2938219)
/**#include <bits/stdc++.h>
#include <deque>
#include <fstream>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
deque <int> dq;
int a[500001];
long long s,n,k;
int main()
{
f>>n>>k;
for (int i=1;i<=n;i++)
{
f>>a[i];
while (!dq.empty()&&a[dq.back()]>a[i])
dq.pop_back();
if (!dq.empty()&&dq.front()==i-k)
dq.pop_front();
dq.push_back(i);
if (i>=k)s+=a[dq.front()];
}
f.close();
g<<s;
g.close();
return 0;
}*/
#include <bits/stdc++.h>
#include <deque>
#include <fstream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int a[500001],n,k,b,bm=-30000,st=500001,sf=500001,x;
deque <int> dq;
int main()
{
f>>n>>k;
for (int i=1; i<=n; i++)
{
f>>a[i];
while (!dq.empty()&&a[dq.back()]>a[i])
dq.pop_back();
if (!dq.empty()&&dq.front()==i-k)
dq.pop_front();
dq.push_back(i);
b=a[dq.front()];
if (b>bm)
{
bm=b;
st=dq.front();
sf=dq.back();
}
else if (b==bm&&dq.front()<st)
{
bm=b;
st=dq.front();
sf=dq.back();
}
else if (dq.front()==st&&dq.back()<sf)
{
bm=b;
st=dq.front();
sf=dq.back();
}
}
f.close();
g<<st<<" "<<sf<<" "<<bm;
g.close();
return 0;
}