Cod sursa(job #1561705)
| Utilizator | Data | 4 ianuarie 2016 14:13:53 | |
|---|---|---|---|
| Problema | Secventa 2 | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.69 kb |
#include <iostream>
#include <fstream>
using namespace std;
int n,k;
int dp[50002],vmin[50002];
int main()
{
ifstream f("secv2.in");
ofstream g("secv2.out");
f>>n>>k;
for(int i=1;i<=n;i++)
{
int x;
f>>x;
dp[i]=dp[i-1]+x;
if(dp[i]<dp[vmin[i-1]])
vmin[i]=i;
else
vmin[i]=vmin[i-1];
}
int best=dp[k],st=1,dr=k;
for(int i=k+1;i<=n;i++)
{
if(dp[i]-dp[vmin[i-k]]>best)
{
best=dp[i]-dp[vmin[i-k]];
dr=i;
st=vmin[i-k]+1;
}
}
g<<st<<" "<<dr<<" "<<best<<'\n';
f.close();
g.close();
return 0;
}
