Submission #1320492
Source Code Expand
#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 Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | square1001 |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 615 Byte |
Status | AC |
Exec Time | 446 ms |
Memory | 237824 KB |
Compile Error
./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]); ^
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 | 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 |