Cod sursa(job #2737475)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 4 aprilie 2021 19:42:20
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");

int v[5000005],p[5000005];

void adaugare(int &st,int &dr,int x,int poz)
{
  while(dr>=st && v[dr]>x)
  {
    v[dr]=0;
    dr--;
  }
  dr++;
  v[dr]=x;
  p[dr]=poz;
}

void stergere(int &st,int &dr,int poz,int k)
{
  if(poz-p[st]>=k)
  {
    p[st]=0;
    st++;
  }
}

void afis(int st,int dr)
{
  for(int i=st;i<=dr;i++)
  {
    fout<<v[i]<<" ";
  }
  fout<<'\n';
}
int main()
{
  long long s=0;
  int n,k,dr,st,q,i;

  fin>>n>>k;
  st=1;
  dr=0;
  for(i=1;i<=k;i++)
  {
    fin>>q;
    adaugare(st,dr,q,i);
    //afis(st,dr);
  }
  s+=v[st];
  for(i=k+1;i<=n;i++)
  {
    fin>>q;
    stergere(st,dr,i,k);
    adaugare(st,dr,q,i);
    s+=v[st];
    //afis(st,dr);
  }
  fout<<s;
  return 0;
}