Submission #2448833
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef complex<double> point;
#define mapii map<int, int>
#define debug(a) cout << #a << ": " << a << endl
#define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
#define fdto(i, r, l) for(int i = (r); i >= (l); --i)
#define fto(i, l, r) for(int i = (l); i <= (r); ++i)
#define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
#define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
#define ii pair<int, int>
#define iii pair<int, ii>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define maxN 100005
#define maxK 305
#define MOD 1000
#define oo 1000000000000000007LL
#define sz(a) (int)a.size()
const double PI = acos(-1.0);
double fRand(double fMin, double fMax)
{
double f = (double)rand() / RAND_MAX;
return fMin + f * (fMax - fMin);
}
template <class T>
T min(T a, T b, T c) {
return min(a, min(b, c));
}
template <class T>
T max(T a, T b, T c) {
return max(a, max(b, c));
}
int n, m, k, a[maxN];
ll dp[maxK][maxN];
int main () {
scanf("%d%d%d", &n, &m, &k);
fto(i, 1, n) scanf("%d", &a[i]);
dp[1][0] = -oo;
fto(j, 1, n) dp[1][j] = a[j];
fto(i, 2, k) {
dp[i][0] = -oo;
deque<int> q;
fto(j, 1, n) {
while (!q.empty() && dp[i-1][q.back()] <= dp[i-1][j-1]) q.pop_back();
q.push_back(j-1);
while (q.front() < j-m) q.pop_front();
dp[i][j] = dp[i-1][q.front()] + 1LL*a[j]*i;
}
}
ll ans = *max_element(dp[k], dp[k]+n+1);
printf("%lld", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Struck Out |
User |
xuanquang1999 |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1756 Byte |
Status |
AC |
Exec Time |
465 ms |
Memory |
235392 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:48:32: 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:49:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
fto(i, 1, n) scanf("%d", &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, 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 |
1 ms |
256 KB |
sample_3.txt |
AC |
2 ms |
2304 KB |
subtask_1_1.txt |
AC |
6 ms |
24832 KB |
subtask_1_2.txt |
AC |
84 ms |
233984 KB |
subtask_1_3.txt |
AC |
454 ms |
235392 KB |
subtask_1_4.txt |
AC |
8 ms |
24960 KB |
subtask_1_5.txt |
AC |
20 ms |
6016 KB |
subtask_1_6.txt |
AC |
32 ms |
155904 KB |
subtask_1_7.txt |
AC |
160 ms |
79744 KB |
subtask_1_8.txt |
AC |
456 ms |
235392 KB |
subtask_1_9.txt |
AC |
47 ms |
233728 KB |
subtask_2_1.txt |
AC |
6 ms |
22784 KB |
subtask_2_2.txt |
AC |
3 ms |
8448 KB |
subtask_2_3.txt |
AC |
4 ms |
14592 KB |
subtask_2_4.txt |
AC |
6 ms |
22784 KB |
subtask_2_5.txt |
AC |
6 ms |
22784 KB |
subtask_2_6.txt |
AC |
6 ms |
22784 KB |
subtask_2_7.txt |
AC |
6 ms |
22784 KB |
subtask_2_8.txt |
AC |
6 ms |
22784 KB |
subtask_2_9.txt |
AC |
4 ms |
16640 KB |
subtask_3_1.txt |
AC |
57 ms |
24448 KB |
subtask_3_2.txt |
AC |
57 ms |
24448 KB |
subtask_3_3.txt |
AC |
55 ms |
24448 KB |
subtask_3_4.txt |
AC |
47 ms |
24192 KB |
subtask_3_5.txt |
AC |
8 ms |
22912 KB |
subtask_3_6.txt |
AC |
35 ms |
14208 KB |
subtask_3_7.txt |
AC |
57 ms |
24448 KB |
subtask_3_8.txt |
AC |
10 ms |
23040 KB |
subtask_3_9.txt |
AC |
58 ms |
24448 KB |
subtask_4_1.txt |
AC |
455 ms |
235392 KB |
subtask_4_10.txt |
AC |
361 ms |
235392 KB |
subtask_4_11.txt |
AC |
461 ms |
235392 KB |
subtask_4_12.txt |
AC |
461 ms |
235392 KB |
subtask_4_13.txt |
AC |
462 ms |
235392 KB |
subtask_4_2.txt |
AC |
465 ms |
235392 KB |
subtask_4_3.txt |
AC |
457 ms |
235392 KB |
subtask_4_4.txt |
AC |
457 ms |
235392 KB |
subtask_4_5.txt |
AC |
389 ms |
200576 KB |
subtask_4_6.txt |
AC |
47 ms |
20352 KB |
subtask_4_7.txt |
AC |
251 ms |
124800 KB |
subtask_4_8.txt |
AC |
449 ms |
235392 KB |
subtask_4_9.txt |
AC |
208 ms |
104320 KB |