Cod sursa(job #3199647)

Utilizator ifrim.claudiaClaudia Ifrim ifrim.claudia Data 2 februarie 2024 10:45:54
Problema Secventa Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
// https://www.infoarena.ro/problema/secventa

// Gigel are un sir de N numere intregi. Toata lumea stie ca o secventa este un subsir de numere
// care apar pe pozitii consecutive in sirul initial. Gigel a definit baza unei secvente ca fiind
// minimul valorilor elementelor din secventa respectiva.

// Cerinta
// Fiind dat un numar natural K, determinati pentru Gigel o secventa de lungime cel putin K cu baza maxima.

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

const int MAX_LIMIT = 500000;
const int MIN = -30000;
const int MAX = 30000;

struct result
{
  int start;
  int end;
  int bmin;
} res;

int n, k, v[MAX_LIMIT];

int min(int a[], int start, int k)
{
  int min = MAX;

  for (int i = start; i < start + k; i++)
  {
    if (a[i] < min)
    {
      min = a[i];
    }
  }

  return min;
}

int main()
{
  fin >> n >> k;
  int bmax = MIN;

  for (int i = 1; i <= n; i++)
  {
    fin >> v[i];
  }

  for (int i = 1; i <= n - k + 1; i++)
  {
    int bmin = min(v, i, k);
    if (bmax < bmin)
    {
      bmax = bmin;
      res.start = i;
      res.end = i + k - 1;
      res.bmin = bmax;
    }
  }

  fout << res.start << " " << res.end << " " << res.bmin << endl;

  return 0;
}