Cod sursa(job #3199657)

Utilizator ifrim.claudiaClaudia Ifrim ifrim.claudia Data 2 februarie 2024 11:48:28
Problema Secventa Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 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 bmin;
} res;

int n, k, v[MAX_LIMIT];

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

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

  for (int i = 1; i <= k; i++)
  {
    if (bmin > v[i])
    {
      bmin = v[i];
    }
  }

  res.start = 1;
  res.bmin = bmin;
  bmax = bmin;

  for (int i = 2; i <= n - k + 1; i++)
  {
    int x = i + k - 1;
    int bmin = MAX;
    while (x >= i)
    {
      if (v[x] < bmin)
      {
        bmin = v[x];
      }
      x--;
    }

    if (bmax < bmin)
    {
      bmax = bmin;
      res.start = i;
      res.bmin = bmax;
    }
  }

  fout << res.start << " " << res.start + k - 1 << " " << res.bmin << endl;

  return 0;
}