Rezultati

Up. imeNalogaJezikRezultatČas oddaje
finalsolution-2017 Ribiči C 100/100OK 11. maj '17 @ 17:13

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 1,488 MiB 0,000 s OK
#2 3/3 38,246 MiB 0,041 s OK
#3 3/3 8,168 MiB 0,011 s OK
#4 3/3 7,578 MiB 0,056 s OK
#5 4/4 11,898 MiB 0,069 s OK
#6 4/4 9,707 MiB 0,056 s OK
#7 4/4 16,008 MiB 0,075 s OK
#8 4/4 44,082 MiB 0,191 s OK
#9 4/4 44,664 MiB 0,282 s OK
#10 4/4 26,910 MiB 0,095 s OK
#11 4/4 44,586 MiB 0,263 s OK
#12 4/4 7,574 MiB 0,056 s OK
#13 4/4 7,617 MiB 0,056 s OK
#14 4/4 7,617 MiB 0,056 s OK
#15 4/4 10,082 MiB 0,063 s OK
#16 4/4 45,004 MiB 0,283 s OK
#17 4/4 44,965 MiB 0,289 s OK
#18 4/4 1,539 MiB 0,000 s OK
#19 4/4 3,547 MiB 0,000 s OK
#20 4/4 3,590 MiB 0,005 s OK
#21 4/4 1,539 MiB 0,000 s OK
#22 4/4 44,590 MiB 0,253 s OK
#23 4/4 44,625 MiB 0,257 s OK
#24 4/4 16,164 MiB 0,017 s OK
#25 4/4 16,168 MiB 0,023 s OK
#26 4/4 20,211 MiB 0,023 s OK

Ocenjevani program (ribici.c):
#include <stdio.h>
#include <stdlib.h>

int N = 0, D = 0, K = 0;
long long R[100002];
long long M[50][100002];

static long long recurse(int ri, int di) {
    if (ri >= N) return 0;
    if (di >= K) return 0;
    if (M[di][ri] != 0) return M[di][ri] - 1;
    int n1 = recurse(ri + 1, di);
    int n2 = recurse(ri + D, di + 1) + (R[ri+D>N?N:ri+D] - R[ri]);
    M[di][ri] = (n1 > n2 ? n1 : n2) + 1;
    return M[di][ri] - 1;
}

int main() {
    int i = 0;
    scanf("%d %d %d", &N, &D, &K);
    for (; i < N; i++) {
        int r = 0;
        scanf("%d", &r);
        R[i+1] = R[i] + r;
    }
    long long tot = recurse(0, 0);
    printf("%lld\n", tot);
    return 0;
}