CODE FESTIVAL 2016 Tournament Round 3 (Parallel)

Submission #1320497

Source codeソースコード

#include <bits/stdc++.h>
int N, M, K, ptr[100009]; long long dp[309][100009];
int main() {
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < N; i++) scanf("%lld", &dp[0][i]);
	for (int i = 1; i < K; i++) {
		int pl = 0, pr = 0;
		for (int j = 0; j < N; j++) {
			if (j >= i) dp[i][j] = dp[i - 1][ptr[pl]] + 1LL * (i + 1) * dp[0][j];
			if (ptr[pl] == j - M) pl++;
			while (pl < pr && dp[i - 1][ptr[pr - 1]] < dp[i - 1][j]) pr--;
			ptr[pr++] = j;
		}
	}
	printf("%lld\n", *std::max_element(dp[K - 1], dp[K - 1] + N));
	return 0;
}

Submission

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

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:4:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &N, &M, &K);
^
./Main.cpp:5:54: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < N; i++) scanf("%lld", &dp[0][i]);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt,sample_3.txt
subtask1 100 / 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 100 / 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 4352 KB
subtask_1_1.txt AC 6 ms 24832 KB
subtask_1_2.txt AC 88 ms 236032 KB
subtask_1_3.txt AC 448 ms 237824 KB
subtask_1_4.txt AC 9 ms 24960 KB
subtask_1_5.txt AC 19 ms 6400 KB
subtask_1_6.txt AC 35 ms 155904 KB
subtask_1_7.txt AC 157 ms 82176 KB
subtask_1_8.txt AC 449 ms 237824 KB
subtask_1_9.txt AC 51 ms 235776 KB
subtask_2_1.txt AC 6 ms 24832 KB
subtask_2_2.txt AC 3 ms 10496 KB
subtask_2_3.txt AC 5 ms 16640 KB
subtask_2_4.txt AC 6 ms 24832 KB
subtask_2_5.txt AC 6 ms 24832 KB
subtask_2_6.txt AC 6 ms 24832 KB
subtask_2_7.txt AC 6 ms 24832 KB
subtask_2_8.txt AC 6 ms 24832 KB
subtask_2_9.txt AC 5 ms 16640 KB
subtask_3_1.txt AC 56 ms 26880 KB
subtask_3_2.txt AC 56 ms 26880 KB
subtask_3_3.txt AC 55 ms 26880 KB
subtask_3_4.txt AC 46 ms 26624 KB
subtask_3_5.txt AC 9 ms 24960 KB
subtask_3_6.txt AC 34 ms 14592 KB
subtask_3_7.txt AC 56 ms 26880 KB
subtask_3_8.txt AC 11 ms 25088 KB
subtask_3_9.txt AC 56 ms 26880 KB
subtask_4_1.txt AC 449 ms 237824 KB
subtask_4_10.txt AC 167 ms 237952 KB
subtask_4_11.txt AC 425 ms 237824 KB
subtask_4_12.txt AC 441 ms 237824 KB
subtask_4_13.txt AC 447 ms 237824 KB
subtask_4_2.txt AC 449 ms 237824 KB
subtask_4_3.txt AC 448 ms 237824 KB
subtask_4_4.txt AC 449 ms 237824 KB
subtask_4_5.txt AC 381 ms 200960 KB
subtask_4_6.txt AC 46 ms 20736 KB
subtask_4_7.txt AC 242 ms 127232 KB
subtask_4_8.txt AC 442 ms 237824 KB
subtask_4_9.txt AC 204 ms 106752 KB