这题枚举出来真分数，然后快排。
当真分数a/b<真分数c/d时，有a*d<b*c
在此给速度榜第一名的QILIN跪了，竟然用hash，不用排序直接输出就可以……

program shuta;
var
i,j,n,max,temp:longint;
a,f:array[0..1000,0..1000] of longint;
path:array[0..1000] of longint;
begin
assign(input,'shuta.in');
assign(output,'shuta.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do
for j:=1 to i do
read(a[i,j]);
f[1,1]:=a[1,1];
for i:=2 to n do
for j:=1 to i do
begin
f[i,j]:=f[i-1,j];
if f[i-1,j]<f[i-1,j-1] then
f[i,j]:=f[i-1,j-1];
f[i,j]:=f[i,j]+a[i,j];
if f[i,j]>max then
begin
max:=f[i,j];
path[n]:=a[i,j];
temp:=j;
end;
end;
for i:=n-1 downto 1 do
begin
if f[i,temp]>f[i,temp-1] then
path[i]:=a[i,temp]
else
begin
path[i]:=a[i,temp-1];
dec(temp);
end;
end;
writeln(max);
for i:=1 to n-1 do
write(path[i],' ');
writeln(path[n]);
close(input);
close(output);
end.

连MST都不会写了。。。
刷水太少了。。。。。。

两个号各提交一次，时间居然一样（精确到微秒= =）

c++er是不是因为标准库？

r最多不对，最大正方形也不对。

O(∩_∩)O~。你一点创新意识都没有。垃圾。

楼上，傻吊。

嘎嘎

原来在windows下一个bool型的函数是会默认返回true的……= =

怎么做？？？

坑跌。不给数据范围：M<=50000

开和不开O2优化差距好大，从0.013s到0.001s。已跪......

严重水题。也有坑点！

谨以此水题保佑所有NOIPer全过，拿国一！！

为啥NlogN的算法还是超时了？

好飘逸的思路……

f[i]表示到i为止的最佳方案。对i，for j=i-1 to 0判断。如果j+1 to i可分配一个教室，则判断min{f[j]+1,f[i]}的大小。
将f数组初始化为最大值，f[0]=0,最后输出f[n]即可。
挺简单的DP题，思路很裸，也不需要特别高的代码能力。就看比赛的时候能不能想得到了。

pascal注意，这题的最后一组数据专门卡二分快排，所以一定用随机快排！

这时间。。。这空间。。。