Pagini recente » Cod sursa (job #754523) | Cod sursa (job #2606315) | Cod sursa (job #2102195) | Cod sursa (job #444695) | Cod sursa (job #1152905)
#include <iostream>
#include <fstream>
#define nmax 50005
#define inf (1<<30)
using namespace std;
int v[nmax], sum[nmax], dp[nmax], ssm[nmax];
int n, k, sol = -inf, lo, hi, x;
int main() {
ifstream f("secv2.in");
ofstream g("secv2.out");
f>>n>>k;
for(int i=1; i<=n; i++) {
f>>v[i];
sum[i] = sum[i-1] + v[i];
ssm[i] = max(ssm[i-1] + v[i], v[i]);
ssm[i] = max(ssm[i], 0);
}
for(int i=k; i<=n; i++) {
dp[i] = max(ssm[i-k] + sum[i] - sum[i-k], sum[i] - sum[i-k]);
if(dp[i] > sol) sol = dp[i], hi = i;
}
//for(int i=1; i<=n; i++) cout<<dp[i]<<" "; cout<<"\n\n";
lo = hi;
x = sol;
while(x) x -= v[lo--];
g<<lo+1<<" "<<hi<<" "<<sol<<"\n";
return 0;
}