(*

Strip of Land (IOI 1999)
Copyright (C) 2000 Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA



 

Per costruire un rettangolo massimale con variazione in altezza limitata,
scandiamo l'input riga per riga e manteniamo in maniera dinamica una matrice
M[i][d] che dice, per ogni colonna i, qual e` il numero massimo di righe di
cui si puo` salire mantenendo la variazione in altezza con l'elemento della
riga corrente nell'intervallo [0-d, C-d], con d=0,1,..,C.

La matrice e` mantenibile in maniera dinamica perche' a fronte di una
nuova riga e` sufficiente fare scorrere la lista di C+1 valori di M
corrispondenti a una colonna di un numero di posti uguale alla differenza
tra l'altezza corrente e quella precedente, e riempire il resto con uni
(lo scorrimento e` verso l'alto o verso il basso a seconda del segno della
differenza).

Una volta che la matrice e` riempita, per ogni larghezza l e` possibile
stabilire la massima altezza di un rettangolo che soddisfa i vincoli e sta
sopra alla riga corrente. Fissiamo una colonna i e un valore di d, e
supponiamo che il vettore a contenga le altezze della riga corrente. Sappiamo
di quanto possiamo al piu` salire nella colonna i mantenendo la variazione
in [0-d, C-d] andando a leggere M[i][d]. Poi ci spostiamo su i-1, andiamo a
vedere la massima ascesa possibile leggendo M[i][d+a[i-1]-a[i]] (sempre che
non debordiamo da M) e la minizziamo con quella corrente, e cosi` via. Si
noti che la condizione imposta implica che anche gli elementi nella colonna
i-1 saranno corretti, perche' le loro altezze saranno nell'intervallo

[a[i-1] - (d+a[i-1]-a[i]), a[i-i]+C - (d+a[i-1]-a[i])] = [a[i]-d, a[i]+C-d]

esattamente come quelli nella colonna i. Ogni volta massimizziamo l'area
del rettangolo ottenuto con quella corrente.

Se l'indice d+a[i-1]-a[i] deborda da M significa che l'altezza
dell'elemento nella colonna i-1 della riga corrente e` gia` al di fuori
dell'intervallo possibile di variazione, e quindi non e` possibile estendere
ulteriormente il rettangolo.

*)


CONST
	MAXC = 10;			(* Massima variazione in altezza *)
	MAXAMP = 700;		(* Massima ampiezza della mappa *)
	MAXALT = 700;		(* Massima altezza della mappa *)
	MAXAMPSOL = 100;	(* Massima ampiezza della soluzione *)

VAR
	(* Matrice riempita tramite programmazione dinamica *)
	M: array[1..MAXAMP, 0..MAXC] of Integer;
	a: array[1..MAXAMP] of Integer;	(* Altezze della riga corrente *)
	U, V, C, i, j, k, l, d, x1, x2, y, alt: Integer;
	t, maxArea, altcorr: LongInt;
	F: Text;

FUNCTION max(a,b: LongInt): LongInt;
BEGIN
	if a<b then max := b else max := a;
END;

FUNCTION min(a,b: LongInt): LongInt;
BEGIN
	if b<a then min := b else min := a;
END;

BEGIN

	ASSIGN(F, '');
	RESET(F);

	READLN(F, U, V, C);

	maxArea := 0;

   (* La matrice M viene inizialmente riempita di uni. *)
	FOR i:=1 to U DO FOR j:=0 to C DO M[i][j] := 1;

   (* Inoltre dobbiamo leggere la prima riga separatamente
   	e costruire il massimo sottosegmento con variazione
      limitata. *)

	FOR i:=1 TO U DO
	BEGIN
		READ(F, a[i]);
		FOR d:=0 TO C DO (* Variazione in [-d, C-d]. *)
		BEGIN
		(* Controlliamo i segmenti di lunghezza al piu` MAXAMSOL ed estremo
			destro in i *)
			FOR j:=i DOWNTO 1 DO
			BEGIN
				if (i-j < MAXAMPSOL)
					AND (a[j] >= a[i]-d) (* Cioe` a[j]-a[i] in [-d, C-d] *)
					AND (a[j] <= a[i]+C-d) THEN
				BEGIN
					if maxArea < i-j+1 THEN
					BEGIN
						maxArea := i-j+1;
						x1 := j;
						x2 := i;
						y := 1;
						alt := 1;
					END;
				END
				ELSE BREAK;
			END;
		END;
	END;
	READLN(F);

	FOR l:=2 TO V DO (* Ora scandiamo le righe rimanenti. *)
	BEGIN
		FOR i:=1 to U DO
		BEGIN
			READ(F, t);
			 (* Troppa variazione, resettiamo M a tutti uni. *)
			IF abs(t-a[i]) > C THEN FOR j:=0 TO C DO M[i][j] := 1
			ELSE IF t > a[i] THEN
			BEGIN
				FOR j:=C DOWNTO t-a[i] DO M[i][j] := M[i][j-(t-a[i])]+1;
            FOR j:=t-a[i]-1 DOWNTO 0 DO M[i][j] := 1;
			END
			ELSE IF t < a[i] THEN
			BEGIN
				FOR j:=0 TO C+(t-a[i]) DO M[i][j] := M[i][j-(t-a[i])]+1;
            FOR j:=C+(t-a[i])+1 TO C DO M[i][j] := 1;
			END
			ELSE FOR j:=0 TO C DO M[i][j] := M[i][j] + 1;

			a[i] := t;

			FOR d:=0 TO C DO	(* Variazione in [-d, C-d]. *)
			BEGIN
				altcorr := High(altcorr);
				FOR j:=i DOWNTO 1 DO
					(* Se la variazione non deborda dai limiti consentiti... *)
					IF (i-j < MAXAMPSOL)
							AND (a[j] >= a[i]-d)
							AND (a[j] <= a[i]+C-d) THEN
					BEGIN
						(* ...aggiorniamo l'altezza massima di un rettangolo
							con base [j,i] che soddisfa i vincoli... *)
						altcorr := min(altcorr, M[j][d+a[j]-a[i]]);
						(* ...e se il rettangolo corrente e` piu` grande del
							migliore che abbiamo trovato finora, lo compriamo. *)
						IF maxArea < altcorr*(i-j+1) THEN
						BEGIN
							maxArea := altcorr*(i-j+1);
							x1 := j;
							x2 := i;
							y := l;
							alt := altcorr;
						END;
					END
					ELSE BREAK;
			END;
		END;
		READLN(F);
	END;

	REWRITE(F);

	WRITELN(F, x1, ' ', y, ' ', x2, ' ', y+alt-1, ' ', maxArea);

END.