CODE FESTIVAL 2016 Tournament Round 3 (Parallel)

Submission #1674592

Source codeソースコード

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;

const int MAX_N = 1 << 18;
const int def = 0;

struct MaxSegTree {
	int n;
	ll dat[2 * MAX_N - 1];
	void init(int n_) {
		n = 1;
		while(n < n_) n *= 2;
		for(int i = 0; i < 2 * n - 1; i++) dat[i] = def;
	}

	void update(int k, ll a) {
		k += n - 1;
		dat[k] = a;
		while(k > 0) k = (k - 1) / 2, dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
	}

	ll query(int a, int b) { return query(a, b, 0, 0, n); }

	ll query(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return def;
		if(a <= l && r <= b) return dat[k];
		ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return max(vl, vr);
	}

	void show() {
		for(int i = 0; i < n; i++) cout << dat[i + n - 1] << " ";
		cout << endl;
	}
} st[2];

ll A[100000];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, M, K;
	cin >> N >> M >> K;
	for(int i = 0; i < N; i++) {
		cin >> A[i];
	}
	st[0].init(N);
	st[1].init(N);

	MaxSegTree* cur = &st[0];
	MaxSegTree* nxt = &st[1];
	for(ll i = 1; i <= K; i++) {
		//cur->show();
		for(int j = 0; j < N; j++) {
			nxt->update(j, 0);
		}
		for(int j = i - 1; j < N; j++) {
			ll sum = A[j] * i;
			sum += cur->query(max(0, j - M), j);
			nxt->update(j, sum);
		}
		swap(cur, nxt);
	}

	//cur->show();
	cout << cur->query(0, N) << endl;
}

Submission

Task問題 A - ストラックアウト / Struck Out
User nameユーザ名 femto
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 TLE
Score得点 500
Source lengthソースコード長 1550 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 200 / 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 300 / 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 2 ms 2304 KB
sample_2.txt AC 2 ms 2304 KB
sample_3.txt AC 2 ms 2304 KB
subtask_1_1.txt AC 2 ms 2304 KB
subtask_1_2.txt AC 414 ms 2688 KB
subtask_1_3.txt TLE
subtask_1_4.txt AC 23 ms 2432 KB
subtask_1_5.txt AC 98 ms 8448 KB
subtask_1_6.txt AC 4 ms 2304 KB
subtask_1_7.txt AC 1697 ms 8448 KB
subtask_1_8.txt TLE
subtask_1_9.txt AC 10 ms 2304 KB
subtask_2_1.txt AC 3 ms 2304 KB
subtask_2_2.txt AC 2 ms 2304 KB
subtask_2_3.txt AC 3 ms 2304 KB
subtask_2_4.txt AC 2 ms 2304 KB
subtask_2_5.txt AC 2 ms 2304 KB
subtask_2_6.txt AC 2 ms 2304 KB
subtask_2_7.txt AC 3 ms 2304 KB
subtask_2_8.txt AC 3 ms 2304 KB
subtask_2_9.txt AC 2 ms 2304 KB
subtask_3_1.txt AC 626 ms 8448 KB
subtask_3_2.txt AC 768 ms 8448 KB
subtask_3_3.txt AC 748 ms 8448 KB
subtask_3_4.txt AC 625 ms 8320 KB
subtask_3_5.txt AC 22 ms 2432 KB
subtask_3_6.txt AC 359 ms 8448 KB
subtask_3_7.txt AC 550 ms 8448 KB
subtask_3_8.txt AC 65 ms 2688 KB
subtask_3_9.txt AC 703 ms 8448 KB
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 400 ms 8448 KB
subtask_4_7.txt TLE
subtask_4_8.txt TLE
subtask_4_9.txt TLE