CODE FESTIVAL 2016 Tournament Round 3 (Parallel)

Submission #1674850

Source codeソースコード

#include <iostream>
#include <vector>
using namespace std;

using int64 = long long;

const int64 MINIMIZE = -2145141919810364364LL;

// 最大値を計算するSegment tree
template <typename T>
struct SegmentTree {
    const T DEFULT_VAL = MINIMIZE;

    vector<T> dat;
    int end;

    SegmentTree(vector<T>& d) {
        int n = d.size();
        end = 1;
        while (end < n) end *= 2;

        dat.resize(2 * end - 1, DEFULT_VAL);
        
        for (int i = 0; i < d.size(); i++) {
            dat[i + end - 1] = d[i];
        }
        for (int i = end - 2; i >= 0; i--) {
            dat[i] = max(dat[2 * i + 1], dat[2 * i + 2]);
        }
    }

    void update(int idx, T a) {
        int id = idx + end - 1;
        dat[id] = a;
        while (id > 0) {
            id = (id - 1) / 2;
            dat[id] = max(dat[id * 2 + 1], dat[id * 2 + 2]);
        }
    }

    T query(int lb, int ub) {
        return query(lb, ub, 0, 0, end);
    }

    T query(int lb, int ub, int id, int node_lb, int node_ub) {
        if (node_ub <= lb || ub <= node_lb) { return DEFULT_VAL; }

        if (lb <= node_lb && node_ub <= ub) { return dat[id]; }
        else {
            T vl = query(lb, ub, id * 2 + 1, node_lb, (node_lb + node_ub) / 2),
              vr = query(lb, ub, id * 2 + 2, (node_lb + node_ub) / 2, node_ub);
            return max(vl, vr);
        }
    }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    vector<int64> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<int64> elts(N + 1, MINIMIZE);
    elts[0] = 0;

    SegmentTree<int64> segtree(elts);
    int64 ans = 0;
    for (int i = 0; i < K; i++) {
        for (int j = N; j >= 1; j--) {
            int64 res = segtree.query(max(0, j - M), j);
            segtree.update(j, res + A[j - 1] * (i + 1));
            ans = max(ans, res + A[j - 1] * (i + 1));

            /*
            if (res + A[j - 1] * (i + 1) >= 0) {
                cerr << "i: " << i << " j: " << j << " result: " << res + A[j - 1] * (i + 1) << endl;
            }
            */
        }
    }
    cout << ans << endl;

    return 0;
}

Submission

Task問題 A - ストラックアウト / Struck Out
User nameユーザ名 ふーらくたる
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 2219 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt,sample_3.txt
subtask1 0 / 100 sample_2.txt,subtask_1_1.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt
subtask2 0 / 200 sample_1.txt,sample_2.txt,sample_3.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_2_9.txt
subtask3 0 / 300 sample_1.txt,sample_2.txt,sample_3.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_2_9.txt,subtask_3_1.txt,subtask_3_2.txt,subtask_3_3.txt,subtask_3_4.txt,subtask_3_5.txt,subtask_3_6.txt,subtask_3_7.txt,subtask_3_8.txt,subtask_3_9.txt
All 0 / 100 sample_1.txt,sample_2.txt,sample_3.txt,sample_1.txt,sample_2.txt,sample_3.txt,subtask_1_1.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_2_9.txt,subtask_3_1.txt,subtask_3_2.txt,subtask_3_3.txt,subtask_3_4.txt,subtask_3_5.txt,subtask_3_6.txt,subtask_3_7.txt,subtask_3_8.txt,subtask_3_9.txt,subtask_4_1.txt,subtask_4_10.txt,subtask_4_11.txt,subtask_4_12.txt,subtask_4_13.txt,subtask_4_2.txt,subtask_4_3.txt,subtask_4_4.txt,subtask_4_5.txt,subtask_4_6.txt,subtask_4_7.txt,subtask_4_8.txt,subtask_4_9.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
subtask_1_1.txt AC 1 ms 256 KB
subtask_1_2.txt AC 321 ms 640 KB
subtask_1_3.txt TLE
subtask_1_4.txt AC 19 ms 512 KB
subtask_1_5.txt AC 105 ms 3840 KB
subtask_1_6.txt WA
subtask_1_7.txt AC 1320 ms 3840 KB
subtask_1_8.txt TLE
subtask_1_9.txt WA
subtask_2_1.txt AC 2 ms 256 KB
subtask_2_2.txt WA
subtask_2_3.txt AC 2 ms 256 KB
subtask_2_4.txt AC 2 ms 256 KB
subtask_2_5.txt WA
subtask_2_6.txt WA
subtask_2_7.txt AC 2 ms 256 KB
subtask_2_8.txt AC 2 ms 256 KB
subtask_2_9.txt AC 2 ms 256 KB
subtask_3_1.txt AC 510 ms 3840 KB
subtask_3_2.txt AC 620 ms 3840 KB
subtask_3_3.txt AC 603 ms 3840 KB
subtask_3_4.txt WA
subtask_3_5.txt AC 18 ms 512 KB
subtask_3_6.txt WA
subtask_3_7.txt AC 450 ms 3840 KB
subtask_3_8.txt AC 53 ms 640 KB
subtask_3_9.txt WA
subtask_4_1.txt TLE
subtask_4_10.txt TLE
subtask_4_11.txt TLE
subtask_4_12.txt TLE
subtask_4_13.txt TLE
subtask_4_2.txt TLE
subtask_4_3.txt TLE
subtask_4_4.txt TLE
subtask_4_5.txt TLE
subtask_4_6.txt AC 335 ms 3840 KB
subtask_4_7.txt TLE
subtask_4_8.txt TLE
subtask_4_9.txt TLE