Submission #1197686

#TimeUsernameProblemLanguageResultExecution timeMemory
1197686TahirAliyev수열 (APIO14_sequence)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> // #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define int long long #define ld long double #define ll long long #define pii pair<int, int> #define all(v) v.begin(), v.end() using namespace std; const int oo = 1e18 + 9; const int MAX = 4000 + 5, LOGMAX = 20, B = 441, MOD = 998244353; struct line{ int k, b; int f(int x){ return x * k + b; } ld inter(line a){ return (ld)(a.b - b) / (ld)(k - a.k); } }; void solve(){ int n, k; cin >> n >> k; k++; int arr[n + 1]; int pre[n + 1]; pre[0] = 0; for(int i = 1; i <= n; i++){ cin >> arr[i]; pre[i] = pre[i - 1] + arr[i]; } vector<int> dp(n + 1, -oo); dp[0] = 0; //dp[i] = (dp[j] - pre[j] * pre[j]) + pre[i] * pre[j]; vector<int> par[k + 1]; for(int j = 1; j <= k; j++){ vector<int> ndp(n + 1, -oo); par[j].resize(n + 1, 0); deque<line> dq; deque<int> id; dq.push_back({pre[j - 1], (dp[j - 1] - pre[j - 1] * pre[j - 1])}); id.push_back(j - 1); for(int i = j; i <= n; i++){ while(dq.size() >= 2 && dq[0].f(pre[i]) < dq[1].f(pre[i])){ dq.pop_front(); id.pop_front(); } ndp[i] = dq[0].f(pre[i]); par[j][i] = id[0]; line a = {pre[i], dp[i] - pre[i] * pre[i]}; while(dq.size() >= 2 && a.k != dq.back().k && a.inter(dq[dq.size()-2]) >= dq.back().inter(dq[dq.size()-2])){ dq.pop_back(); id.pop_back(); } while(dq.size() >= 2 && a.k == dq.back().k && a.b >= dq.back().b){ dq.pop_back(); id.pop_back(); } if(!dq.size() || dq.back().k != a.k){ dq.push_back(a); id.push_back(i); } } swap(ndp, dp); } cout << dp[n] << '\n'; vector<int> v; int i = n; while(i != 0){ if(i != n) v.push_back(i); i = par[k][i]; k--; } reverse(all(v)); if(!v.size()) v.push_back(1); for(int a : v) cout << a << ' '; cout << '\n'; } signed main(){ // ios::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); int t = 1; // cin >> t; 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...