Submission #2448808
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[0][0] = 0;
fto(j, 1, n) dp[0][j] = -oo;
fto(i, 1, 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 |
100 |
Code Size |
1753 Byte |
Status |
WA |
Exec Time |
485 ms |
Memory |
236160 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 |
0 / 200 |
0 / 300 |
0 / 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 |
86 ms |
233984 KB |
subtask_1_3.txt |
AC |
467 ms |
236160 KB |
subtask_1_4.txt |
AC |
8 ms |
24960 KB |
subtask_1_5.txt |
AC |
21 ms |
6784 KB |
subtask_1_6.txt |
AC |
31 ms |
155904 KB |
subtask_1_7.txt |
AC |
165 ms |
80512 KB |
subtask_1_8.txt |
AC |
468 ms |
236160 KB |
subtask_1_9.txt |
AC |
47 ms |
233728 KB |
subtask_2_1.txt |
AC |
6 ms |
22784 KB |
subtask_2_2.txt |
WA |
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 |
5 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 |
59 ms |
25216 KB |
subtask_3_2.txt |
AC |
58 ms |
25216 KB |
subtask_3_3.txt |
AC |
57 ms |
25216 KB |
subtask_3_4.txt |
WA |
48 ms |
24832 KB |
subtask_3_5.txt |
AC |
8 ms |
22912 KB |
subtask_3_6.txt |
WA |
36 ms |
14976 KB |
subtask_3_7.txt |
AC |
58 ms |
25216 KB |
subtask_3_8.txt |
AC |
11 ms |
23040 KB |
subtask_3_9.txt |
WA |
60 ms |
25216 KB |
subtask_4_1.txt |
AC |
465 ms |
236160 KB |
subtask_4_10.txt |
WA |
382 ms |
236160 KB |
subtask_4_11.txt |
WA |
485 ms |
236160 KB |
subtask_4_12.txt |
WA |
484 ms |
236160 KB |
subtask_4_13.txt |
WA |
482 ms |
236160 KB |
subtask_4_2.txt |
WA |
478 ms |
236160 KB |
subtask_4_3.txt |
AC |
469 ms |
236160 KB |
subtask_4_4.txt |
AC |
466 ms |
236160 KB |
subtask_4_5.txt |
AC |
397 ms |
201344 KB |
subtask_4_6.txt |
AC |
48 ms |
21120 KB |
subtask_4_7.txt |
WA |
258 ms |
125568 KB |
subtask_4_8.txt |
AC |
462 ms |
236160 KB |
subtask_4_9.txt |
AC |
214 ms |
105088 KB |