Submission #1209944

#TimeUsernameProblemLanguageResultExecution timeMemory
1209944giaminhhaFeast (NOI19_feast)C++20
100 / 100
129 ms12168 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define eb emplace_back #define pu push #define ins insert #define fi first #define se second #define all(a) a.begin(),a.end() #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); #define int ll typedef pair<int, int> pii; const int mod = 2147483647; const int inf = 1e18; const int N = 3e5 + 5; int n; int a[N]; pii lambda(int mid){ pii dp[n + 1][2]; dp[0][0] = make_pair(0, 0); dp[0][1] = make_pair(a[0] - mid, 1); for(int i = 1; i < n; i++){ dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); dp[i][1] = max(make_pair(dp[i - 1][0].fi + a[i] - mid, dp[i - 1][0].se + 1), make_pair(dp[i - 1][1].fi + a[i], dp[i - 1][1].se)); } return max(dp[n - 1][0], dp[n - 1][1]); } signed main(){ fastio int k; cin >> n >> k; for(int i = 0; i < n; i++) cin >> a[i]; int left = 0, right = inf, kq; while(left < right){ int mid = (left + right + 1) / 2; pii ans = lambda(mid); if(ans.se >= k) left = mid; else right = mid - 1; } int ans = lambda(left).fi + left * k; cout << ans; 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...