Pagini recente » Cod sursa (job #3190874) | Cod sursa (job #2380047) | Cod sursa (job #393058) | Cod sursa (job #3150727) | Cod sursa (job #2464550)
#include <bits/stdc++.h>
#define NM 100005
#define val first
#define poz second
#define pii pair<int,int>
#define pb push_back
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
int n,k,st,dr,ind,sMax,s[NM];
pii v[NM];
deque <pii> dq;
void Read();
void Solve();
int main()
{ Read();
Solve();
f.close();
g.close();
return 0;
}
void Read()
{ f>>n>>k;
for(int nr,i=1; i<=n; i++)
{ f>>nr;
s[i]=s[i-1]+nr;
}
}
void Solve()
{ for(int i=0; i<=n-k; i++)
{ if(!dq.empty())
{ while(s[i]<=dq.back().val)
{ dq.pop_back();
if(dq.empty())
break;
}
}
dq.pb({s[i],i});
v[i+k]=dq.front();
}
sMax=s[k]-v[k].val;
st=v[k].poz;
dr=k;
for(int i=k+1; i<=n; i++)
if(s[i]-v[i].val>=sMax)
{ sMax=s[i]-v[i].val;
st=v[i].poz+1;
dr=i;
}
g<<st<<' '<<dr<<' '<<sMax;
}