Submission #1253805

#TimeUsernameProblemLanguageResultExecution timeMemory
1253805abdullah_Feast (NOI19_feast)C++20
4 / 100
166 ms9816 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]; mxG = g[i]; } else if (dp[i] - pre[i - 1] == mxDp) { mxG = min(mxG, g[i]); } } return {dp[n], g[n]}; }; int l = 1, r = 1e18, 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...