CODE FESTIVAL 2016 Tournament Round 3 (Parallel)

Submission #1320492

Source codeソースコード

#include <cstdio>
#include <algorithm>
#pragma warning(disable : 4996)
using namespace std;
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", *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ソースコード長 615 Byte
File nameファイル名
Exec time実行時間 446 ms
Memory usageメモリ使用量 237824 KB

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:7: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:8: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 1 ms 2176 KB
sample_2.txt AC 1 ms 2176 KB
sample_3.txt AC 1 ms 4224 KB
subtask_1_1.txt AC 5 ms 24704 KB
subtask_1_2.txt AC 115 ms 235904 KB
subtask_1_3.txt AC 444 ms 237696 KB
subtask_1_4.txt AC 8 ms 24832 KB
subtask_1_5.txt AC 18 ms 6272 KB
subtask_1_6.txt AC 30 ms 155776 KB
subtask_1_7.txt AC 156 ms 82048 KB
subtask_1_8.txt AC 446 ms 237696 KB
subtask_1_9.txt AC 46 ms 235648 KB
subtask_2_1.txt AC 5 ms 24704 KB
subtask_2_2.txt AC 3 ms 10368 KB
subtask_2_3.txt AC 4 ms 16512 KB
subtask_2_4.txt AC 5 ms 24704 KB
subtask_2_5.txt AC 5 ms 24704 KB
subtask_2_6.txt AC 5 ms 24704 KB
subtask_2_7.txt AC 5 ms 24704 KB
subtask_2_8.txt AC 5 ms 24704 KB
subtask_2_9.txt AC 4 ms 16512 KB
subtask_3_1.txt AC 55 ms 26752 KB
subtask_3_2.txt AC 55 ms 26752 KB
subtask_3_3.txt AC 54 ms 26752 KB
subtask_3_4.txt AC 45 ms 26624 KB
subtask_3_5.txt AC 8 ms 24832 KB
subtask_3_6.txt AC 33 ms 14464 KB
subtask_3_7.txt AC 55 ms 26752 KB
subtask_3_8.txt AC 10 ms 24960 KB
subtask_3_9.txt AC 55 ms 26752 KB
subtask_4_1.txt AC 445 ms 237696 KB
subtask_4_10.txt AC 161 ms 237824 KB
subtask_4_11.txt AC 420 ms 237696 KB
subtask_4_12.txt AC 438 ms 237696 KB
subtask_4_13.txt AC 444 ms 237696 KB
subtask_4_2.txt AC 445 ms 237696 KB
subtask_4_3.txt AC 445 ms 237696 KB
subtask_4_4.txt AC 446 ms 237696 KB
subtask_4_5.txt AC 378 ms 200832 KB
subtask_4_6.txt AC 45 ms 20608 KB
subtask_4_7.txt AC 240 ms 127104 KB
subtask_4_8.txt AC 439 ms 237696 KB
subtask_4_9.txt AC 203 ms 106624 KB