Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 3,141 MiB 0,004 s OK
#2 3/3 5,809 MiB 0,034 s OK
#3 3/3 4,438 MiB 0,010 s OK
#4 3/3 3,367 MiB 0,033 s OK
#5 4/4 3,367 MiB 0,027 s OK
#6 4/4 3,367 MiB 0,027 s OK
#7 4/4 3,344 MiB 0,033 s OK
#8 4/4 3,340 MiB 0,033 s OK
#9 4/4 28,445 MiB 0,414 s OK
#10 4/4 11,551 MiB 0,160 s OK
#11 4/4 27,445 MiB 0,426 s OK
#12 4/4 8,574 MiB 5,069 s OK
#13 4/4 13,164 MiB 0,252 s OK
#14 4/4 13,262 MiB 0,051 s OK
#15 4/4 13,727 MiB 0,063 s OK
#16 4/4 31,980 MiB 0,421 s OK
#17 4/4 32,109 MiB 0,414 s OK
#18 4/4 3,332 MiB 0,004 s OK
#19 4/4 3,258 MiB 0,004 s OK
#20 4/4 3,344 MiB 0,004 s OK
#21 4/4 3,328 MiB 0,004 s OK
#22 4/4 27,445 MiB 0,415 s OK
#23 4/4 27,535 MiB 0,413 s OK
#24 4/4 4,680 MiB 0,016 s OK
#25 4/4 4,805 MiB 0,016 s OK
#26 4/4 4,902 MiB 0,022 s OK

Ocenjevani program (n4.cpp):
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <tuple>
#include <algorithm>
#include <utility>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

typedef long long ll;

int solve(int curpos, int len, vector<int>& r, int k, int d, vector<vector<int>>& memo, vector<int>& prec) {
    if (memo[k][curpos] != -1) return memo[k][curpos];
    int res = 0;
    int opt1 = 0;
    if (k > 0) opt1 = prec[curpos] + solve(curpos + d, len, r, k - 1, d, memo, prec);
    else opt1 = prec[curpos];
    int opt2 = 0;
    if (curpos + (k + 1) * d < len) opt2 = solve(curpos + 1, len, r, k, d, memo, prec);
    res = opt1 > opt2 ? opt1 : opt2;
    memo[k][curpos] = res;
    return res;
}

int main(void) {
    cin.tie(nullptr);
    cin.sync_with_stdio(false);

    int n, d, k;
    cin >> n >> d >> k;
    vector<int> r(n);
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }
    if (k * d >= n) {
        int res = 0;
        for (int i = 0; i < n; i++) {
            res += r[i];
        }
        cout << res << endl;
        return 0;
    }
    vector<int> prec(n - d + 1, 0);
    for (int i = 0; i < n - d + 1; i++) {
        for (int j = 0; j < d; j++) {
            prec[i] += r[i + j];
        }
    }
    vector<vector<int>> memo(k, vector<int>(n, -1));
    int res = solve(0, n, r, k - 1, d, memo, prec);
    cout << res << endl;

    return 0;
}