Cod sursa(job #2439758)

Utilizator eutu33eu tu el ea eutu33 Data 16 iulie 2019 19:40:39
Problema Secventa 2 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream in ("secv2.in");
    ofstream out ("secv2.out");

	int n, k;
	in >> n >> k;
	long long vec[n];
	/// valoare,index
	pair <long long,int> minim[n],maxim[n];
	in>>vec[0];
	minim[0].first=vec[0];
	minim[0].second=1;
	for(int i=1;i<n;i++)
    {
        int a;
        in>>a;
        vec[i]=vec[i-1]+a;
        if(vec[i]<minim[i-1].first)
        {
            minim[i].first=vec[i];
            minim[i].second=i+1;
        }
        else
            minim[i]=minim[i-1];
    }
    maxim[n-1].first=vec[n-1];
    maxim[n-1].second=n;
    for(int i=n-2;i>=0;i--)
    {
        if(vec[i]>maxim[i+1].first)
        {
            maxim[i].first=vec[i];
            maxim[i].second=i+1;
        }
        else
            maxim[i]=maxim[i+1];
    }
    long long maxsuma=-1250000009,inceput=0,sfarsit=0;
    for(int i=0;i<n;i++)
    {
        int dif = maxim[i].second - minim[i].second;
        int suma = maxim[i].first-minim[i].first;
        if(dif<0)
            dif*=-1;
        if(suma>maxsuma && dif>=k)
        {
            inceput=min(maxim[i].second,minim[i].second);
            sfarsit=max(maxim[i].second,minim[i].second);
            maxsuma=suma;
        }
    }
    out<<inceput+1<<" "<<sfarsit<<" "<<maxsuma;
    /*cout<<"min\tmax\n";
    for(int i=0;i<n;i++)
    {
        cout<<minim[i].first<<"\t"<<maxim[i].first<<endl;
    }*/
    return 0;
}