제출 #393052

#제출 시각아이디문제언어결과실행 시간메모리
393052arujbansal수열 (APIO14_sequence)C++17
71 / 100
520 ms131076 KiB
#include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #include <array> #include <stack> #include <queue> #include <random> #include <numeric> #include <functional> #include <chrono> #include <utility> #include <iomanip> #include <assert.h> using namespace std; void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define rng_seed(x) mt19937 rng(x) #define all(x) (x).begin(), (x).end() #define sz(x) (int) (x).size() #define int long long const int MXN = 1e5 + 5, INF = 1e18; int N, K; int A[MXN], dp[2][MXN], pref[MXN], trace[205][MXN]; void dnc(int l, int r, int i, int optl, int optr) { if (l > r) return; int cur = i & 1; int mid = (l + r) / 2; pair<int, int> best = {-INF, -INF}; for (int j = optl; j < min(mid, optr + 1); j++) { int new_val = dp[cur ^ 1][j] + (pref[mid] - pref[j]) * (pref[N] - pref[mid]); if (new_val > best.first) best = make_pair(new_val, j); } dp[cur][mid] = best.first; trace[i][mid] = best.second; dnc(l, mid - 1, i, optl, best.second); dnc(mid + 1, r, i, best.second, optr); } void solve() { cin >> N >> K; for (int i = 1; i <= N; i++) { cin >> A[i]; pref[i] = pref[i - 1] + A[i]; } for (int i = 0; i < 2; i++) for (int j = 0; j < MXN; j++) dp[i][j] = -INF; dp[0][0] = 0; for (int i = 1; i <= K; i++) dnc(i, N, i, i - 1, N - 1); pair<int, int> best = {-INF, -INF}; for (int j = 1; j < N; j++) best = max(best, make_pair(dp[K & 1][j], j)); cout << best.first << "\n"; int cur_k = K; while (cur_k && best.second) { cout << best.second << " "; best.second = trace[cur_k--][best.second]; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int TC = 1; // cin >> TC; while (TC--) 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...