TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

jezerca.c    915 b      izvorni kod rešenja
jezerca.checker.c    291 b      program za testiranje
jezerca.tests.rar    6,758,706 b      test primeri

zadatak: Jezerca

Perica već nekoliko meseci provodi dane kraj računara igrajući igru Jezerca. Na početku igre se na ekranu pojavi pravougaona mreža kvadratića na kojoj je prikazan reljef nekog predela u obliku stubića raznih visina koji se nižu jedan za drugim. Zatim preko cele širine ekrana počinje padati kiša. Ona popunjava udubljenja u reljefu, a višak nestaje na levom i desnom kraju ekrana (tj. na stubićima na levom i desnom kraju se uopšte ne zadržava). Kiša prestaje kada se popune sva udubljenja (tako da sva kiša koja padne odlazi na krajeve ekrana i gubi se). Voda koja je napunila udubljenja obrazuje određen broj jezera (vodene površine odvojene bar jednim vertikalnim stubom od drugih vodenih površina).

Perica u tom trenutku treba da izračuna koliko ima kvadratića popunjenih vodom u onom jezeru u kome se zadržalo najviše vode (tj. ima najviše popunjenih kvadratića). Napiši program koji će Perici pomoći da odredi broj kvadratića u jezeru sa najviše kvadratića.

Ulaz:

U prvom redu ulaznog fajla jezerca.in nalazi se ceo broj n (1 ≤ n ≤ 100000) i to je ukupan broj stubića u reljefu. U svakom od sledećih n redova nalazi se po jedan ceo broj i oni predstavljaju visine stubića u redosledu u kome se oni prikazani na ekranu (od levog kraja prema desnom kraju). Visine stubića su između 1 i 10000.

Izlaz:

U prvi red izlaznog fajla jezerca.out treba ispisati broj kvadratića popunjenih vodom u jezeru u kome ima najviše kvadratića popunjenih vodom. Ako ne postoji niti jedno jezero, štampati broj nula (0).

Primer:

jezerca.in          jezerca.out
23
2
3
3
4
2
3
1
3
3
5
2
2
4
6
8
7
4
5
6
3
2
1
1
    
8

Objašnjenje:

Slika prikazuje izgled reljefa, kao i raspored jezera nakon popunjavanja svih udubljenja. Kao što se sa slike vidi ima tri jezera koja imaju 8, 7 i 3 popunjena kvadratića.

fajl: jezerca.c
/*
ZADATAK: jezerca
JEZIK: c
*/
# include <stdio.h>

# define MAXN 1000000

long n;
long mz;
int a[MAXN], ml[MAXN], md[MAXN];

int citaj() {
  long i;
  scanf("%ld", &n);
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]);
  return(0);
}

void resi() {
  long k;
  long i;
  long mm;
  long tz;
  for (ml[0] = 0, i = 1; i < n; i++)
    if (a[i-1] > ml[i-1]) ml[i] = a[i-1]; else ml[i] = ml[i-1];
  for (md[n-1] = 0, i = n-2; i >= 0; i--)
    if (a[i+1] > md[i+1]) md[i] = a[i+1]; else md[i] = md[i+1];
  mz = 0; tz = 0;
  for (k = 0, i = 1; i < n-1; i++) {
    if (ml[i] < md[i]) mm = ml[i]; else mm = md[i];
    if (mm <= a[i]) {
      if (tz > mz) mz = tz;
      tz = 0;
    } else {
      tz += mm-a[i];
    }
  }
  if (tz > mz) mz = tz;
}

void pisi() {
  printf("%ld\n", mz);
}

int main() {
  if (citaj()) {
    exit(1);
  }
  resi();
  pisi();
  return 0;
}