Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 3,238 MiB 0,004 s OK
#2 3/3 33,898 MiB 0,202 s OK
#3 3/3 8,742 MiB 0,046 s OK
#4 3/3 79,176 MiB 0,181 s OK
#5 4/4 79,801 MiB 1,831 s OK
#6 4/4 64,930 MiB 1,204 s OK
#7 4/4 79,859 MiB 2,050 s OK
#8 4/4 77,016 MiB 2,270 s OK
#9 4/4 79,934 MiB 2,301 s OK
#10 4/4 24,965 MiB 0,695 s OK
#11 4/4 79,934 MiB 2,336 s OK
#12 4/4 6,172 MiB 0,110 s OK
#13 4/4 6,379 MiB 0,122 s OK
#14 4/4 6,359 MiB 0,128 s OK
#15 4/4 7,762 MiB 0,171 s OK
#16 4/4 79,961 MiB 2,393 s OK
#17 4/4 79,930 MiB 2,368 s OK
#18 4/4 3,262 MiB 0,004 s OK
#19 4/4 5,266 MiB 0,004 s OK
#20 4/4 5,281 MiB 0,004 s OK
#21 4/4 3,234 MiB 0,004 s OK
#22 4/4 75,242 MiB 2,271 s OK
#23 4/4 79,934 MiB 2,165 s OK
#24 4/4 15,879 MiB 0,088 s OK
#25 4/4 6,801 MiB 0,106 s OK
#26 4/4 18,652 MiB 0,112 s OK

Ocenjevani program (main.cpp):
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1<<17;
const int maxk = 55;

int dp[maxk][maxn];

int LSOne(int x) {
    return x&(-x);
}

struct SegmentTree {
    vector<int > st;
    int n;
    int left(int p) { return p<< 1;}
    int right(int p) {return (p<<1) + 1; }

    int rmq(int p, int L, int R, int i, int j) {
        if(i>R || j< L ) return 0;
        if(L >= i && R <= j) return st[p];

        int p1 = rmq(left(p), L, (L+R)/2, i, j);
        int p2 = rmq(right(p), (L+R)/2 + 1, R, i, j);

        return max(p1, p2);
    }

    SegmentTree() { }
    void set_size(int _n) {
        n = 1;
        while(n<_n) n*=2;
        st.resize(2*n, 0);
    }

    int rmq(int i, int j) {
        return rmq(1, 0, n-1, i, j);
    }

    void update(int pos, int val) {
        int p = n + pos;
        st[p] = val;
        p/=2;

        while(p > 0) {
            int p1 = st[left(p)];
            int p2 = st[right(p)];
            st[p] = max(p1, p2);
            p /= 2;
        }
    }
} st[maxk];

int max_score(int b, int pos) {
    if(pos < 0) return 0;
    return st[b].rmq(0, pos);
    //return *max_element(dp[b], dp[b]+pos+1);
}

void update_max(int b, int pos, int val) {
    st[b].update(pos, val);
}

int d[maxn];

int sum(int i, int j) {
    return d[j+1] - d[i];
}

int main() {
    int N, D, K;

    cin>>N>>D>>K;

    vector<int> r;

    for (int i=0; i<N; i++) {
        int rr;
        cin>>rr;
        r.push_back(rr);
        d[i+1] = d[i] + rr;
    }

    for(int b=0;b<=K;b++) {
        st[b].set_size(N+1);
    }

    for(int b = 1;b<=K;b++) {
        for(int pos = D-1;pos<N;pos++) {
            dp[b][pos] = sum(pos - D + 1, pos) + max_score(b-1, pos-D); //pos-D is included in max
            update_max(b, pos, dp[b][pos]);
        }
    }

    auto m = max_element(dp[K], dp[K] + N);

    printf("%d\n", *m);

    return 0;
}