Rezultati

Up. imeNalogaJezikRezultatČas oddaje
jam-2017 Ribiči Java 100/100OK 11. maj '17 @ 18:19

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 31,672 MiB 0,000 s OK
#2 3/3 52,609 MiB 0,801 s OK
#3 3/3 56,980 MiB 0,435 s OK
#4 3/3 101,438 MiB 1,460 s OK
#5 4/4 106,512 MiB 1,691 s OK
#6 4/4 104,027 MiB 1,634 s OK
#7 4/4 97,656 MiB 2,966 s OK
#8 4/4 105,086 MiB 3,033 s OK
#9 4/4 97,367 MiB 3,176 s OK
#10 4/4 80,352 MiB 2,050 s OK
#11 4/4 102,348 MiB 2,643 s OK
#12 4/4 76,934 MiB 2,216 s OK
#13 4/4 81,676 MiB 1,617 s OK
#14 4/4 82,648 MiB 2,821 s OK
#15 4/4 76,805 MiB 2,854 s OK
#16 4/4 108,750 MiB 2,309 s OK
#17 4/4 108,984 MiB 2,180 s OK
#18 4/4 36,719 MiB 0,000 s OK
#19 4/4 33,387 MiB 0,000 s OK
#20 4/4 36,707 MiB 0,000 s OK
#21 4/4 42,293 MiB 0,000 s OK
#22 4/4 104,816 MiB 4,477 s OK
#23 4/4 100,266 MiB 3,695 s OK
#24 4/4 51,844 MiB 0,595 s OK
#25 4/4 51,805 MiB 0,677 s OK
#26 4/4 54,258 MiB 0,647 s OK

Ocenjevani program (Ribici.java):
import java.util.Scanner;

public class Ribici {

    static int d;

    static int sums[];

    static long memo[][];

    public static long re(int n, int k) {
        if(k  == 0 || n-d+1 < 0)
            return 0;
        if(memo[n][k] != 0)
            return memo[n][k] - 1;
        long nobene = re(n-1, k);
        long ja = re(n-d, k-1) + sums[n-d+1];
        long r = Math.max(nobene, ja);
        memo[n][k] = r + 1;
        return r;
    }

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        d = sc.nextInt();
        int k = sc.nextInt();

        int rollingSum = 0;
        sums = new int[n - d + 1];
        int a[] = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            rollingSum += a[i];
            if(i >= d) {
                rollingSum -= a[i-d];
            }

            if(i >= d - 1) {
                sums[i - d + 1] = rollingSum;
            }
        }

        memo = new long[n][k + 1];
        System.out.println(re(n-1, k));
    }

}
/*
10 3 2
7 1 2 1 3 5 4 0 1 2
 */