// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, k;
cin >> n >> k;
vector<int> c(n+1);
vector<int> s(n+1);
vector<vector<int>> dp(n+1, vector<int> (k+1, -1e18));
vector<vector<int>> dpinv(n+2, vector<int> (k+1, -1e18));
vector<vector<bool>> opt(n+1, vector<bool> (k+1, 0));
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= n+1; i++) {
dpinv[i][0] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j] = dp[i-1][j]-c[i];
if (dp[i][j] < dp[i-1][j-1]-c[i]+s[i]) {
opt[i][j] = 1;
dp[i][j] = dp[i-1][j-1]-c[i]+s[i];
}
//cout << dp[i][j] << " - ";
}
//cout << endl;
}
//cout << "STOP" << endl;
for (int i = n; i > 0; i--) {
for (int j = 1; j <= k; j++) {
dpinv[i][j] = dpinv[i+1][j]-c[i];
if (dpinv[i][j] < dpinv[i+1][j-1]-c[i]+s[i]) {
dpinv[i][j] = dpinv[i+1][j-1]-c[i]+s[i];
}
//cout << i << " " << j << ": " << dpinv[i][j] << endl;
}
//cout << endl;
}
int ans = -1e18;
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[i][k]);
}
cout << ans << endl;
vector<bool> res(n+1, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
//cout << opt[i][j] << " " << dp[i][j] << " " << dpinv[i+1][k-j] << " " << c[i] << " " << s[i] << endl;
if (opt[i][j] && dp[i][j]+dpinv[i+1][k-j] == ans) res[i] = 1;
}
//cout << endl;
}
for (int i = 1; i <= n; i++) cout << res[i];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |