Pagini recente » Cod sursa (job #3291786) | Cod sursa (job #2714422) | Cod sursa (job #913978) | Cod sursa (job #3250623) | Cod sursa (job #1122117)
/// Craciun Catalin
/// Secv2
/// Programare dinamica
#include <fstream>
#include <iostream>
#include <map>
struct cheie{
int LEFT, RIGHT;
};
#define NMax 50005
#define INF 0x3f3f3f
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
unsigned int n,k;
int A[NMax];
long long S[NMax];
unsigned int st, dr, auxSt;
long bestSum;
long loserSum;
void inteligent()
{
bestSum=-INF;
loserSum=INF;
for(int i=k;i<=n;++i)
{
if(A[i-k]<loserSum)
{
loserSum=A[i -k];
auxSt=i-k+1;
}
if(A[i]-loserSum>bestSum)
{
bestSum=A[i]-loserSum;
st=auxSt;
dr=i;
}
}
g<<st<<' '<<dr<<' '<<bestSum<<'\n';
g.close();
}
void brute()
{
bool found=false;
long long maxim;
unsigned int st, dr;
for (unsigned int i=1;i<=n;i++)
S[i]=S[i-1]+A[i];
for (unsigned int i=1;i<=n-k+1;i++)
{
for (unsigned int j=i+k-1;j<=n;j++)
if (!found)
{
maxim=S[j]-S[i-1];
st=i;
dr=j;
found=true;
}
else if (S[j]-S[i-1]>maxim)
{
maxim=S[j]-S[i-1];
st=i;
dr=j;
}
}
g<<st<<' '<<dr<<' '<<maxim<<'\n';
g.close();
}
void citire()
{
f>>n>>k;
for (unsigned int i=1;i<=n;i++)
f>>A[i];
f.close();
}
int main()
{
citire();
inteligent();
return 0;
}