Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 3,086 MiB 0,004 s OK
#2 3/3 5,527 MiB 0,034 s OK
#3 3/3 5,527 MiB 0,016 s OK
#4 3/3 27,457 MiB 0,117 s OK
#5 4/4 27,500 MiB 0,123 s OK
#6 4/4 27,453 MiB 0,117 s OK
#7 4/4 27,496 MiB 0,141 s OK
#8 4/4 27,496 MiB 0,245 s OK
#9 4/4 27,457 MiB 0,318 s OK
#10 4/4 15,711 MiB 0,100 s OK
#11 4/4 27,453 MiB 0,305 s OK
#12 4/4 27,496 MiB 0,104 s OK
#13 4/4 27,492 MiB 0,110 s OK
#14 4/4 27,453 MiB 0,110 s OK
#15 4/4 27,457 MiB 0,110 s OK
#16 4/4 27,457 MiB 0,276 s OK
#17 4/4 27,461 MiB 0,234 s OK
#18 4/4 3,328 MiB 0,004 s OK
#19 4/4 3,285 MiB 0,004 s OK
#20 4/4 3,324 MiB 0,004 s OK
#21 4/4 3,285 MiB 0,004 s OK
#22 4/4 27,453 MiB 0,277 s OK
#23 4/4 27,488 MiB 0,311 s OK
#24 4/4 5,527 MiB 0,022 s OK
#25 4/4 5,488 MiB 0,022 s OK
#26 4/4 5,527 MiB 0,022 s OK

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

using namespace std;

int ribe[100000][2],a,b,dp[100000][50];

int rek(int s, int k){
    if (s >= a || k == -1) return 0;
    if (dp[s][k] != -1) return dp[s][k];
    dp[s][k] = max(ribe[s][1]+rek(s+b,k-1),rek(s+1,k));
    return dp[s][k];
}

int main()
{
    int c,d,e,f;
    cin >> a >> b >> c;
    c--;
    for (int i = 0; i < a; i++){
        cin >> ribe[i][0];
        for (int i2 = 0; i2 < (c+1); i2++){
            dp[i][i2] = -1;
        }
    }
    ribe[0][1] = 0;
    for (int i = 0; i < b; i++){
        ribe[0][1] += ribe[i][0];
    }
    for (int i = 1; i <= a-b; i++){
        ribe[i][1] = ribe[i-1][1] - ribe[i - 1][0] + ribe[i+b - 1][0];
    }
    for (int i = a - b +1; i < a; i++){
        ribe[i][1] = ribe[i-1][1] - ribe[i-1][0];
    }
    cout << rek(0,c);
    return 0;
}