Submission #1674653
Source Code Expand
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;
int n, m, k;
int dp[310][33];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
vector<int> a(n);
rep(i, 0, n){
cin >> a[i];
}
if(n == m){
vector<P> d;
rep(i, 0, n) d.push_back(P(a[i], i));
sort(all(d));
reverse(all(d));
vector<bool> f(n, false);
rep(i, 0, k) f[d[i].second] = true;
int ans = 0, now = 1;
rep(i, 0, n){
if(f[i]){
ans += now * a[i];
now++;
}
}
cout << ans << endl;
return 0;
}
assert(n <= 300 && k <= 30);
rep(i, 0, 310) rep(j, 0, 33) dp[i][j] = -1;
rep(i, 0, 310) dp[i][0] = 0;
rep(i, 1, n + 1){
rep(j, 1, k + 1){
for(int l = i - 1; l >= max(0LL, i - m); l--){
if(dp[l][j - 1] == -1) continue;
dp[i][j] = max(dp[i][j], dp[l][j - 1] + j * a[i - 1]);
}
}
}
int ans = 0;
// rep(i, 0, n + 1){
// rep(j, 0, k + 1){
// cout << dp[i][j] << " ";
// }
// cout << endl;
// }
rep(i, 0, n + 1){
ans = max(ans, dp[i][k]);
}
cout << ans << endl;
}
Submission Info
Submission Time |
|
Task |
A - Struck Out |
User |
treeone |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1661 Byte |
Status |
RE |
Exec Time |
108 ms |
Memory |
3188 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
subtask3 |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
1 ms |
384 KB |
sample_2.txt |
AC |
1 ms |
256 KB |
sample_3.txt |
AC |
1 ms |
384 KB |
subtask_1_1.txt |
WA |
1 ms |
256 KB |
subtask_1_2.txt |
WA |
3 ms |
768 KB |
subtask_1_3.txt |
WA |
20 ms |
3188 KB |
subtask_1_4.txt |
WA |
2 ms |
512 KB |
subtask_1_5.txt |
AC |
20 ms |
3188 KB |
subtask_1_6.txt |
AC |
1 ms |
256 KB |
subtask_1_7.txt |
WA |
20 ms |
3188 KB |
subtask_1_8.txt |
WA |
20 ms |
3188 KB |
subtask_1_9.txt |
WA |
1 ms |
256 KB |
subtask_2_1.txt |
AC |
4 ms |
384 KB |
subtask_2_2.txt |
AC |
1 ms |
384 KB |
subtask_2_3.txt |
AC |
2 ms |
384 KB |
subtask_2_4.txt |
WA |
1 ms |
256 KB |
subtask_2_5.txt |
AC |
1 ms |
384 KB |
subtask_2_6.txt |
AC |
1 ms |
256 KB |
subtask_2_7.txt |
AC |
2 ms |
384 KB |
subtask_2_8.txt |
AC |
4 ms |
384 KB |
subtask_2_9.txt |
AC |
3 ms |
384 KB |
subtask_3_1.txt |
RE |
107 ms |
1024 KB |
subtask_3_2.txt |
RE |
108 ms |
1024 KB |
subtask_3_3.txt |
RE |
108 ms |
1024 KB |
subtask_3_4.txt |
RE |
106 ms |
896 KB |
subtask_3_5.txt |
RE |
97 ms |
256 KB |
subtask_3_6.txt |
RE |
107 ms |
1024 KB |
subtask_3_7.txt |
RE |
108 ms |
1024 KB |
subtask_3_8.txt |
RE |
101 ms |
384 KB |
subtask_3_9.txt |
RE |
106 ms |
1024 KB |
subtask_4_1.txt |
RE |
108 ms |
1024 KB |
subtask_4_10.txt |
RE |
107 ms |
1024 KB |
subtask_4_11.txt |
RE |
107 ms |
1024 KB |
subtask_4_12.txt |
RE |
107 ms |
1024 KB |
subtask_4_13.txt |
RE |
108 ms |
1024 KB |
subtask_4_2.txt |
RE |
107 ms |
1024 KB |
subtask_4_3.txt |
RE |
107 ms |
1024 KB |
subtask_4_4.txt |
RE |
106 ms |
1024 KB |
subtask_4_5.txt |
RE |
108 ms |
1024 KB |
subtask_4_6.txt |
RE |
107 ms |
1024 KB |
subtask_4_7.txt |
RE |
107 ms |
1024 KB |
subtask_4_8.txt |
RE |
107 ms |
1024 KB |
subtask_4_9.txt |
RE |
107 ms |
1024 KB |