Rezultati

Up. imeNalogaJezikRezultatČas oddaje
lisperator-2017 Ribiči C++ 0/100Prekoračen čas (TLE) 11. maj '17 @ 18:43

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 3,047 MiB 0,004 s OK
#2 0/3 2,977 MiB 10,644 s Prekoračen čas
#3 0/3 2,813 MiB 10,656 s Prekoračen čas
#4 3/3 3,848 MiB 0,080 s OK
#5 4/4 3,816 MiB 0,080 s OK
#6 4/4 3,852 MiB 0,080 s OK
#7 4/4 3,852 MiB 0,080 s OK
#8 0/4 3,664 MiB 10,647 s Prekoračen čas
#9 0/4 3,500 MiB 10,641 s Prekoračen čas
#10 0/4 3,281 MiB 10,648 s Prekoračen čas
#11 0/4 3,500 MiB 10,641 s Prekoračen čas
#12 4/4 3,852 MiB 3,765 s OK
#13 4/4 3,813 MiB 0,226 s OK
#14 4/4 3,852 MiB 0,080 s OK
#15 0/4 3,660 MiB 10,647 s Prekoračen čas
#16 0/4 3,500 MiB 10,660 s Prekoračen čas
#17 0/4 3,500 MiB 10,660 s Prekoračen čas
#18 4/4 3,090 MiB 0,004 s OK
#19 0/4 2,738 MiB 10,650 s Prekoračen čas
#20 0/4 2,906 MiB 10,650 s Prekoračen čas
#21 4/4 3,086 MiB 0,004 s OK
#22 0/4 3,500 MiB 10,655 s Prekoračen čas
#23 0/4 3,668 MiB 10,640 s Prekoračen čas
#24 0/4 2,813 MiB 10,662 s Prekoračen čas
#25 0/4 2,809 MiB 10,650 s Prekoračen čas
#26 0/4 2,977 MiB 10,656 s Prekoračen čas

Ocenjevani program (Source.cpp):
#include <iostream>
using namespace std;
int N, D, K;
int* depth;
int* sumAtDepth;

int fishCount(int sum, int currentDepth, int daysLeft)
{
	if (currentDepth + D > N)
		return -1;

	int count = sumAtDepth[currentDepth];
	if (count == -1)
	{
		count = 0;
		for (int i = currentDepth; i != currentDepth + D; i++)
			count += depth[i];
		sumAtDepth[currentDepth] = count;
	}

	if (daysLeft == 0)
	{
		return sum + count;
	}
		

	int max = 0;
	for (int i = currentDepth + D; i <= N - D + 1; i++)
	{
		int newCount = fishCount(count + sum, i, daysLeft - 1);
		if (newCount > max)
			max = newCount;
	}
	return max;
}

int main()
{
	
	cin >> N >> D >> K;
	K--;
	depth = new int[N];
	sumAtDepth = new int[N];
	
	for (int i = 0; i != N; i++)
	{
		cin >> depth[i];
		sumAtDepth[i] = -1;
	}

	if (D * K >= N)
	{
		int sum = 0;
		for (int i = 0; i != N; i++)
			sum += depth[i];
		cout << sum << endl;
	}
	else
	{
		int count = fishCount(0, 0, K);
		for (int i = 1; i != N; i++)
		{
			int newCount = fishCount(0, i, K);
			if (newCount > count)
				count = newCount;
		}

		cout << count << endl;
	}
	

	//system("pause");

	return 0;
}