# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1253800 | abdullah_ | Feast (NOI19_feast) | C++20 | 629 ms | 192420 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pp;
#define all(a) (a).begin(), (a).end()
#define what_is(x) cerr << #x << " is " << x << '\n';
#define print(a) for (const auto &x : (a)) cout << x << ' '; cout << '\n';
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e15;
void solve() {
int n, k; cin >> n >> k;
vector<int> a(n + 1);
vector<int> pre(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
// The maximum sum when taking 3 segments and some segments may be big
// we will add some random value into the
auto check = [&] (int val)->pp {
vector<int> dp(n + 1), g(n + 1);
int mxDp = 0, mxG = 0;
for (int i = 1; i <= n; ++i) {
int sum = pre[i] + mxDp - val;
dp[i] = dp[i - 1];
g[i] = g[i - 1];
if (sum > dp[i]) {
dp[i] = sum;
g[i] = mxG + 1;
}
if (dp[i] - pre[i - 1] > mxDp) {
mxDp = dp[i] - pre[i - 1];
mxG = g[i];
} else if (dp[i] - pre[i - 1] == mxDp) {
mxG = min(mxG, g[i]);
}
}
// print(dp);
// print(g);
// cout << "val: " << val << endl;
return {dp[n], g[n]};
};
int l = 1, r = 1000, pos = -1;
int res = 0;
while (l <= r) {
int mid = (l + r) / 2;
auto [ans, count] = check(mid);
// cout << ans << ' ' << count << '\n';
if (count <= k) {
res = max(res, ans + mid * count);
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << res << endl;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int tt = 1;
// cin >> tt;
while (tt--) {
solve();
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |