Letöltés: fg_fazekasd.dpr {$A+,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S-,T-,U-,V+,W-,X+,Y+,Z1} {$MINSTACKSIZE $00004000} {$MAXSTACKSIZE $00100000} {$IMAGEBASE $00400000} {$APPTYPE CONSOLE} PROGRAM fazekasd; CONST ch = '1'; inputFile = 'FAZEKAS'+ch+'.BE'; outputFile = 'FAZEKAS'+ch+'.KIX'; maxn = 10000; VAR N, K: INTEGER; list: ARRAY [1..maxn] OF RECORD E: BYTE; END; cache: ARRAY [1..maxn+1] OF INTEGER; choice: ARRAY [1..maxn] OF BYTE; PROCEDURE Load; VAR T: Text; i: INTEGER; BEGIN Assign(T, inputFile); Reset(T); ReadLn(T, N, K); FOR i:= 1 TO N DO BEGIN ReadLn(T, list[i].e); END; Close(T); END; {Load} PROCEDURE Best(elso_targy: INTEGER); VAR i: INTEGER; max: INTEGER; {a berakott targyak e. ideje} ido: INTEGER; {max + a maradek targyak e. ideje} tmp: INTEGER; BEGIN max:= 0; tmp:= elso_targy+K-1; IF tmp > N THEN tmp:= N; FOR i:= elso_targy TO tmp DO {minimum kereses} BEGIN IF list[i].e > max THEN max:= list[i].e; ido:= max + cache[i+1]; {*} IF (cache[elso_targy] = -1) OR (ido < cache[elso_targy]) THEN BEGIN cache[elso_targy]:= ido; choice[elso_targy]:= i-elso_targy+1; END; END; END; {Best} PROCEDURE Process; VAR T: Text; i: INTEGER; BEGIN Assign(T, outputFile); Rewrite(T); FOR i:= 1 TO N DO cache[i]:= -1; {a minimum keresesben ezt kihasznaljuk!} cache[N+1]:= 0; FOR i:= N DOWNTO 1 DO Best(i); WriteLn(T, cache[1]); i:= 1; WHILE i <= N DO BEGIN WriteLn(T, i, ' ', i+choice[i]-1); i:= i+choice[i]; END; Close(T); END; {Process} BEGIN Load; Process; END. |