Submission #892794

#TimeUsernameProblemLanguageResultExecution timeMemory
892794ayallaFeast (NOI19_feast)C++14
100 / 100
165 ms9552 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long int #define pb push_back #define pi pair<int, int> #define pii pair<int, pi> #define fir first #define sec second #define MAXN 300005 #define mod 998244353 int n, k; int a[MAXN]; pi solve(int lambda) { vector<int> dp(n + 1); vector<int> cnt(n + 1); dp[0] = 0; cnt[0] = 0; pi best = {0, 0}; pi curr = {0, 0}; auto f = [&](pi x) { return dp[x.fir] + x.sec; }; for (int i = 1; i <= n; i++) { dp[i] = dp[i - 1]; cnt[i] = cnt[i - 1]; int id = i - 1; best.sec += a[id]; if (f(best) < f({i - 1, a[id]})) { best = {i - 1, a[id]}; } else if (f(best) == f({i - 1, a[id]}) && cnt[best.fir] > cnt[i - 1]) { best = {i - 1, a[id]}; } int s = dp[best.fir] + best.sec - lambda; if (s > dp[i]) { dp[i] = s; cnt[i] = cnt[best.fir] + 1; } } return {dp[n], cnt[n]}; } int aliens_trick() { int l = 0, r = 1e15; while (l < r) { int mid = (l + r) >> 1; pi ans = solve(mid); (ans.sec > k) ? l = mid + 1 : r = mid; } pi ans = solve(l); return ans.fir + (l * ans.sec); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; cout << aliens_trick() << endl; return 0; }

Compilation message (stderr)

feast.cpp: In function 'std::pair<long long int, long long int> solve(long long int)':
feast.cpp:29:6: warning: variable 'curr' set but not used [-Wunused-but-set-variable]
   29 |   pi curr = {0, 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...