Submission #1320497
Source Code Expand
#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 Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | square1001 |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 550 Byte |
Status | AC |
Exec Time | 449 ms |
Memory | 237952 KB |
Compile Error
./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]); ^
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 200 / 200 | 300 / 300 | 100 / 100 | ||||||||||
Status |
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt |
subtask1 | 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 | 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 | 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 | 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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
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 |