제출 #446167

#제출 시각아이디문제언어결과실행 시간메모리
446167nishuz수열 (APIO14_sequence)C++17
49 / 100
82 ms131076 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define ll long long #define ld long double #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define pb push_back #define eb emplace_back #define F first #define S second #define mp make_pair #define random mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) template <typename T> using oset = tree <pair <T, T>, null_type, less <pair <T, T>>, rb_tree_tag, tree_order_statistics_node_update>; template <typename Container> void Print(Container& container, int starting) { auto Start = container.begin() + starting, End = container.end(); while (Start != End) cout << *(Start++) << " "; cout << '\n'; } template <typename T> void print(T&& t) {cout << t << '\n';} template <typename T, typename... Args> void print(T&& t, Args&&... args) { cout << t << " "; print(forward<Args>(args)...); } const int MAXN = 1e5 + 5, MAXK = 205; int64_t a[MAXN], dp[2][MAXN], par[MAXK][MAXN], n; void compute(int64_t l, int64_t r, int64_t optl, int64_t optr, int64_t k) { if (l > r) return; int64_t mid = (l + r) >> 1, row = k & 1; pair <int64_t, int64_t> best = make_pair(-1, -1); for (int64_t i = optl; i < min(mid, optr + 1); ++i) best = max(best, make_pair(dp[row ^ 1][i] + (a[n] - a[mid]) * (a[mid] - a[i]), i)); dp[row][mid] = best.first; par[k][mid] = best.second; int64_t opt = best.second; compute(l, mid - 1, optl, opt, k); compute(mid + 1, r, opt, optr, k); } inline void solve() { int64_t k; cin >> n >> k; memset(a, 0, sizeof a); for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i] += a[i - 1]; } for (int i = 0; i <= k; ++i) { for (int j = 0; j <= n; ++j) { par[i][j] = -1; } } for (int i = 0; i <= n; ++i) { dp[0][i] = dp[1][i] = -1; } dp[0][0] = 0; for (int i = 1; i <= k; ++i) { compute(0, n, 0, n, i); } pair <int64_t, int64_t> ans = mp(-1, -1); for (int64_t i = 1; i <= n; ++i) { ans = max(ans, mp(dp[k & 1][i], i)); } print(ans.F); vector <int64_t> seq(k); int64_t cur = k - 1; while (k) { seq[cur--] = ans.S; ans.S = par[k--][ans.S]; } Print(seq, 0); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T = 1; // cin >> T; for (int test = 1; test <= T; ++test) { // cout << "Case #" << test << ": "; 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...