Submission #6424521

---

Source Code Expand

unittest
{
	assert( [ "5", "4", "3", "1", "2", "1" ].parse.expand.solve == 2 );
	assert( [ "7", "93", "249", "150", "958", "442", "391", "25" ].parse.expand.solve == 3 );
	assert( [ "4", "100", "100", "100", "100" ].parse.expand.solve == 1 );
	assert( [ "6", "5", "10", "15", "20", "25", "30" ].parse.expand.solve == 6 );
	assert( [ "15", "3", "1", "4", "1", "5", "9", "2", "6", "5", "3", "5", "8", "9", "7", "9" ].parse.expand.solve == 6 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	auto ws = new long[ n ];
	foreach( ref w; ws )
	{
		input.popFront;
		w = input.front.to!( long );
	}
	return tuple( ws );
}

auto solve( long[] ws )
{
	long[] ds;
	foreach( w; ws )
	{
		auto pi = -1L;
		auto pd = long.max;
		foreach( i, d; ds )
		{
			if( d < w || pd < d ) continue;
			pi = i;
			pd = d;
		}
		if( 0 <= pi ) ds[ pi ] = w;
		else          ds ~= w;
	}
	return ds.length;
}

Submission Info

Judge Result