Skip to content

Instantly share code, notes, and snippets.

@tarawa
Created July 20, 2013 11:35
Show Gist options
  • Save tarawa/6044728 to your computer and use it in GitHub Desktop.
Save tarawa/6044728 to your computer and use it in GitHub Desktop.
POJ1952 (Pascal)
const
maxn=5000;
var
n,i,j:longint;
a,f,g,next:array [0..maxn+10] of int64;
function max(p,q:int64):int64;
begin
if p>q then exit(p) else exit(q);
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
a[0]:=maxlongint;
for i:=1 to n+1 do
for j:=0 to i-1 do
if a[j]>a[i] then f[i]:=max(f[i],f[j]+1);
g[0]:=1;
for i:=1 to n do
begin
j:=i-1;
while (j>0) and (not ((a[i]=a[j]) and (f[i]=f[j]))) do dec(j);
next[i]:=j;
end;
for i:=1 to n+1 do
for j:=next[i] to i-1 do
if (a[j]>a[i]) and (f[i]=f[j]+1) then inc(g[i],g[j]);
writeln(f[n+1]-1,' ',g[n+1]);
end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment