Submission #561622

#TimeUsernameProblemLanguageResultExecution timeMemory
561622AndreyPavlovFeast (NOI19_feast)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> using namespace std; #define rep(s,t,i) for(int i=s;i<t;++i) #define per(s,t,i) for(int i=s;i>=t;--i) #define F first #define S second #define repp(a,i) for (auto i: a) #define pb push_back #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define int long long template <class T> using pq = priority_queue<T, vector <T>, less <T>>; template <class T> using pqr = priority_queue<T, vector <T>, greater <T>>; using pii = pair <int, int>; template <class T> using vc = vector <T>; const int N = 100, inf = 1e9; pii dp[N + 2]; int a[N + 1], p[N + 1], n; pii solve (int A) { rep(0, N + 1, i) dp[i] = {-inf, 0}; dp[0] = {0, 0}; for (int i = 1; i <= n + 1; ++i) { dp[i] = dp[i - 1]; for (int j = 0; j < i; ++j) { dp[i] = max(dp[i], {dp[j].F + (p[i] - p[j - 1]) - A, dp[j].S + 1}); } } return dp[n + 1]; } void solve () { int k; cin >> n >> k; rep(0, n, i) cin >> a[i + 1], p[i + 1] = p[i] + a[i]; p[n + 1] = p[n] + a[n]; int l = 0, r = inf; while (r - l > 1) { int m = (l + r) / 2; if (solve(m).S <= k) r = m; else l = m; } cout << solve(r).F + k * r << '\n'; } int32_t main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1;while(t--){solve();} }
#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...