Pagini recente » Cod sursa (job #2363653) | Cod sursa (job #3124967) | Arhiva de probleme | Cod sursa (job #3136702) | Cod sursa (job #3156979)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <tuple>
using namespace std;
ifstream cin("secv2.in");
ofstream cout("secv2.out");
int main()
{
int n,k;
cin>>n>>k;
vector<int>v(n);
int sum=0;
for(int i=0;i<n;i++)
{
cin>>v[i];
if(i<k)
{
sum+=v[i];
}
}
vector<pair<int,int> >maxsum(n,{0,0});
maxsum[0].first=v[0];
maxsum[0].second=0;
int maxseq=v[0];
int pos=0;
for(int i=1;i<n;i++)
{
if(v[i]>maxseq+v[i])
{
maxseq=v[i];
pos=i;
}
else
{
maxseq+=v[i];
}
maxsum[i]={maxseq,pos};
}
int res=sum;
int st=0,en=k;
for(int i=k;i<n;i++)
{
sum+=v[i]; sum-=v[i-k];
//res=max(res,sum)
//res=max(res,sum+maxsum[i-k]));
if(res<sum)
{
res=sum;
st=i-k+1;
en=i;
}
if(res<sum+maxsum[i-k].first)
{
res=sum+maxsum[i-k].first;
st=maxsum[i-k].second;
en=i;
}
}
cout<<st+1<<" "<<en+1<<" "<<res;
return 0;
}