Pagini recente » Cod sursa (job #3325829) | Cod sursa (job #3350501) | Cod sursa (job #3348587) | Monitorul de evaluare | Cod sursa (job #3355899)
#include <fstream>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int n,k;
int v[50005];
long long int ps[50005];
long long int dp[50005];
int l[50005];
void read()
{
fin >> n >> k;
for(int i = 1; i <= n; ++i){
fin >> v[i];
ps[i] = ps[i - 1] + v[i];
}
}
void solve()
{
dp[k] = ps[k];
l[k] = 1;
for(int i = k + 1; i <= n; ++i){
if(dp[i - 1] + v[i] >= ps[i] - ps[i - k]){
dp[i] = dp[i - 1] + v[i];
l[i] = l[i - 1];
}
else{
dp[i] = ps[i] - ps[i - k];
l[i] = i - k + 1;
}
}
long long int maxS = -2500000000;
int st, dr;
for(int i = k; i <= n; ++i){
if(dp[i] > maxS){
maxS = dp[i];
st = l[i];
dr = i;
}
}
fout << st << ' ' << dr << ' ' << maxS;
}
int main()
{
read();
solve();
return 0;
}