Submission #1001806
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define MAX_N 100005 #define MAX_M 100005 #define MAX_K 305 int N, M, K; LL A[MAX_N]; void input() { cin >> N >> M >> K; for (size_t i = 0; i < N; i++) { scanf("%lld", &A[i]); } } LL dp[MAX_N][MAX_K]; deque<pair<LL, int>> numList; void init() { numList.clear(); } void pushList(LL val, int num) { pair<LL, int> a = make_pair(val, num); while(numList.size()){ if(numList[numList.size()-1] < a){ numList.pop_back(); } else{ break; } } numList.push_back(a); } LL getList(int minNum){ while(numList.size()){ if(numList[0].second < minNum){ numList.pop_front(); } else{ return numList[0].first; } } return -1; } LL solve() { memset(dp, -1, sizeof(dp)); for (size_t i = 0; i < N; i++) { dp[i][1] = A[i]; } for (int k = 1; k < K; k++) { init(); for (int n = 0; n < N; n++) { if(getList(max(0, n-M)) >= 0){ LL tmp = getList(max(0, n-M)) + (LL)(k+1)*A[n]; dp[n][k+1] = max(dp[n][k+1], tmp); } pushList(dp[n][k], n); } } LL ret = 0; for (size_t i = 0; i < N; i++) { ret = max(ret, dp[i][K]); } return ret; } signed main() { input(); cout << solve() << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | takoshi |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1393 Byte |
Status | AC |
Exec Time | 1749 ms |
Memory | 239360 KB |
Compile Error
./Main.cpp: In function ‘void input()’: ./Main.cpp:18:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld", &A[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, 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 | 236 ms | 238592 KB |
sample_2.txt | AC | 237 ms | 238592 KB |
sample_3.txt | AC | 237 ms | 238592 KB |
subtask_1_1.txt | AC | 239 ms | 238592 KB |
subtask_1_2.txt | AC | 358 ms | 238592 KB |
subtask_1_3.txt | AC | 1563 ms | 239360 KB |
subtask_1_4.txt | AC | 243 ms | 238592 KB |
subtask_1_5.txt | AC | 268 ms | 239360 KB |
subtask_1_6.txt | AC | 238 ms | 238592 KB |
subtask_1_7.txt | AC | 693 ms | 239360 KB |
subtask_1_8.txt | AC | 1565 ms | 239360 KB |
subtask_1_9.txt | AC | 242 ms | 238592 KB |
subtask_2_1.txt | AC | 237 ms | 238592 KB |
subtask_2_2.txt | AC | 239 ms | 238592 KB |
subtask_2_3.txt | AC | 237 ms | 238592 KB |
subtask_2_4.txt | AC | 238 ms | 238720 KB |
subtask_2_5.txt | AC | 237 ms | 238592 KB |
subtask_2_6.txt | AC | 238 ms | 238592 KB |
subtask_2_7.txt | AC | 238 ms | 238592 KB |
subtask_2_8.txt | AC | 236 ms | 238592 KB |
subtask_2_9.txt | AC | 237 ms | 238592 KB |
subtask_3_1.txt | AC | 375 ms | 239360 KB |
subtask_3_2.txt | AC | 387 ms | 239360 KB |
subtask_3_3.txt | AC | 382 ms | 239360 KB |
subtask_3_4.txt | AC | 353 ms | 239104 KB |
subtask_3_5.txt | AC | 243 ms | 238592 KB |
subtask_3_6.txt | AC | 314 ms | 239360 KB |
subtask_3_7.txt | AC | 375 ms | 239360 KB |
subtask_3_8.txt | AC | 251 ms | 238592 KB |
subtask_3_9.txt | AC | 384 ms | 239360 KB |
subtask_4_1.txt | AC | 1574 ms | 239360 KB |
subtask_4_10.txt | AC | 1557 ms | 239360 KB |
subtask_4_11.txt | AC | 1749 ms | 239360 KB |
subtask_4_12.txt | AC | 1682 ms | 239360 KB |
subtask_4_13.txt | AC | 1633 ms | 239360 KB |
subtask_4_2.txt | AC | 1654 ms | 239360 KB |
subtask_4_3.txt | AC | 1578 ms | 239360 KB |
subtask_4_4.txt | AC | 1665 ms | 239360 KB |
subtask_4_5.txt | AC | 1394 ms | 239360 KB |
subtask_4_6.txt | AC | 369 ms | 239360 KB |
subtask_4_7.txt | AC | 984 ms | 239360 KB |
subtask_4_8.txt | AC | 1609 ms | 239360 KB |
subtask_4_9.txt | AC | 885 ms | 239360 KB |