Rezultati

Up. imeNalogaJezikRezultatČas oddaje
EOF-2017 Ribiči C++ 100/100OK 11. maj '17 @ 18:01

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 23,074 MiB 0,016 s OK
#2 3/3 23,492 MiB 0,040 s OK
#3 3/3 23,492 MiB 0,028 s OK
#4 3/3 27,836 MiB 0,110 s OK
#5 4/4 27,840 MiB 0,123 s OK
#6 4/4 27,844 MiB 0,110 s OK
#7 4/4 27,840 MiB 0,141 s OK
#8 4/4 27,879 MiB 0,275 s OK
#9 4/4 27,879 MiB 0,403 s OK
#10 4/4 25,402 MiB 0,130 s OK
#11 4/4 27,875 MiB 0,391 s OK
#12 4/4 27,840 MiB 0,104 s OK
#13 4/4 27,840 MiB 0,104 s OK
#14 4/4 27,879 MiB 0,110 s OK
#15 4/4 27,836 MiB 0,117 s OK
#16 4/4 27,879 MiB 0,398 s OK
#17 4/4 27,875 MiB 0,416 s OK
#18 4/4 23,082 MiB 0,016 s OK
#19 4/4 23,078 MiB 0,016 s OK
#20 4/4 23,078 MiB 0,016 s OK
#21 4/4 23,117 MiB 0,016 s OK
#22 4/4 27,840 MiB 0,362 s OK
#23 4/4 27,840 MiB 0,396 s OK
#24 4/4 23,531 MiB 0,059 s OK
#25 4/4 23,492 MiB 0,028 s OK
#26 4/4 23,492 MiB 0,059 s OK

Ocenjevani program (Ribici.cpp):
#include <iostream>
#include <cstring>

using namespace std;

int a[100002];
int memo[100002][52];


int N, D, K;

int dp(int i, int k){
	//for(int kkk = 0; kkk < K-k+1; kkk++)cout<<" ";
	
	//cout<<"dp("<<i<<','<<k<<"): ";
	if(i == N) return 0;
	if(k == 0) return 0;
	if(memo[i][k] != -1) return memo[i][k];
	
	//cout<<endl;
	int next = min(i + D, N);
	memo[i][k] = max(dp(i + 1, k), a[next] - a[i] + dp(next, k - 1));
	//for(int kkk = 0; kkk < K-k+1; kkk++) cout<<"-";
	
	//cout<<memo[i][k]<<endl;
	return memo[i][k];
	
}



int main(){
	cin>>N>>D>>K;
	memset(memo, -1, sizeof(memo));
	a[0] = 0;
	for(int iii = 1; iii <= N; iii++){
		cin>>a[iii];
		a[iii] += a[iii - 1];
	}
	/*for(int iii = 0; iii <= N; iii++){
		cout<<a[iii]<<endl;	
	}*/
	cout<<dp(0, K);
}