#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define reb(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fs first
#define se second
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd (chrono::steady_clock::now().time_since_epoch().count());
ll Rand (ll L, ll R) { return uniform_int_distribution<ll> (L, R)(rd); }
const int N = 2e3 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
int n, m, K;
int a[N];
int Mn[N][N];
ll dp[N][N][2], pre[N][N], suf[N][N], g[N][N][2], pos[N];
int dd[N];
vector<ll> V = {0};
int cpr (int X) {
return lower_bound(ALL(V), X) - V.begin();
}
void compress () {
rep (i, 1, n) V.pb(a[i]);
sort (ALL(V));
V.resize(unique(ALL(V)) - V.begin());
m = SZ(V) - 1;
}
void solution() {
cin >> n >> K;
rep (i, 1, n) cin >> a[i];
rep (i, 1, n) {
Mn[i][i] = a[i];
rep (j, i + 1, n) Mn[i][j] = min(Mn[i][j - 1], a[j]);
}
// rep (i, 1, n) {
// int de = 1;
// while (a[i] == a[i + 1]) ++i, ++de;
//// if (a[i] == 2) cout << de <<"\n";
// }
ll res = 0;
compress();
memset(dp, -0x3f, sizeof dp);
memset(pre, -0x3f, sizeof pre);
memset(suf, -0x3f, sizeof suf);
memset(g, -0x3f, sizeof g);
rep (j, 1, m) suf[0][j] = 0;
rep (j, 1, m) {
dp[0][j][1] = 0;
}
rep (i, 1, n) {
int bound = cpr(a[i]);
rep (j, 1, bound) {
if (i > K) {
dp[i][j][1] = max(pre[i - 1][j] + V[j], dp[i][j][1]);
dp[i][j][1] = max(g[i - K][j][0] + V[j], dp[i][j][1]);
}
else dp[i][j][1] = dp[i - 1][j][1] + V[j];
if (i <= n - K + 1) {
dp[i][j][0] = suf[i - 1][j] + V[j];
if (i > K) dp[i][j][0] = max(g[i - K][j][1] + V[j], dp[i][j][0]);
}
else dp[i][j][0] = dp[i - 1][j][0] + V[j];
}
rep (j, 1, m) pre[i][j] = max(pre[i][j - 1], dp[i][j][1]);
reb (j, m, 1) suf[i][j] = max(suf[i][j + 1], dp[i][j][0]);
int mnp = cpr(Mn[i][i + K - 1]);
rep (j, 1, mnp) {
rep (k, 0, 1) {
g[i][j][k] = max(g[i][j - 1][k], dp[i][j][k] + V[j] * (K - 1));
}
}
}
// cout << dp[K][1][1] <<" "<<1LL * a[1] * K <<"\n";
cout << max(pre[n][m], suf[n][1]) <<"\n";
}
int main () {
freopen("c.INP","r",stdin);
freopen("c.OUT","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--) solution();
}
Compilation message
sequence.cpp: In function 'void solution()':
sequence.cpp:53:8: warning: unused variable 'res' [-Wunused-variable]
53 | ll res = 0;
| ^~~
sequence.cpp: In function 'int main()':
sequence.cpp:94:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | freopen("c.INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
sequence.cpp:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen("c.OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
53 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
51 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
48 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
