Pagini recente » Cod sursa (job #1551363) | cel_mai_mare_olimpicar_2019_oni2011 | Cod sursa (job #1271196) | Monitorul de evaluare | Cod sursa (job #1479979)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("ssm.in",ios::in);
ofstream g("ssm.out",ios::out);
int sum[7000001],n,k;
void ssm()
{
f>>n;
for(int i = 0 ; i < n ;i++)
f>>sum[i];
//obs : folosesc acelasi vector deoarece in caz contrat as folosi prea multa memorie
int minSum = 0 ,maxSum = -2000000 ,lIndex = 1,rIndex = 1 ,auxSum,aux_lIndex = 1;
for (int i = 1 ; i < n ; i++)
{
// actualizez daca e cazul minSum comparandu-l cu sum[i-1]
if(sum[i-1] < minSum)
{
minSum = sum[i-1];
aux_lIndex = i+1;
}
//creez sum[i]
sum[i] = sum[i-1] + sum[i];
// vad ce subsir care se termina in i are suma maxima
auxSum = sum[i] - minSum;
// compar subsirul cu maxSum, actualizand indicii
if(auxSum > maxSum)
{
maxSum = auxSum;
rIndex = i + 1;
lIndex = aux_lIndex;
}
}
//cout<<maxSum<<" "<<lIndex<<" "<<rIndex;
g<<maxSum<<" "<<lIndex<<" "<<rIndex;
}
void ssm_optimizat()
{
//variabile
int minSum = 0 ,maxSum = -2000000 ,lIndex = 1,rIndex = 1, aux_lIndex = 1,curSum,prevSum;
f>>n>>k;
f>>prevSum;
for(int i = 1 ; i < n ; i++)
{
f>>curSum;
curSum+=prevSum;
//verific daca subsirul de dinainte are suma minima
if(prevSum < minSum)
{
minSum = prevSum;
aux_lIndex = i+1;
}
//verific daca subsirul de suma maxima care se termina pe poz i este subsir de suma max
if(maxSum < curSum - minSum)
{
if(i+1 - aux_lIndex > k)
{
maxSum = curSum - minSum;
rIndex = i + 1;
lIndex = aux_lIndex;
}
}
//curSum devine prevSum pt iteratia urmatoare
prevSum = curSum;
}
//cout<<maxSum<<" "<<lIndex<<" "<<rIndex;
g<<maxSum<<" "<<lIndex<<" "<<rIndex;
}
int main()
{
//ssm();
ssm_optimizat();
f.close();
g.close();
}