제출 #1085076

#제출 시각아이디문제언어결과실행 시간메모리
1085076ZeroCool수열 (APIO14_sequence)C++14
0 / 100
32 ms12396 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define ar array const int LOG = 20; const int MOD = 1e9 + 7; const int INF = 1e18; const int N = 3005; struct LINE { int a, b, id ; LINE (int a, int b, int id ) : a(a), b(b), id(id) {} int operator() (const int &x) { return a * x + b; } }; struct convex_hull_trick { vector<LINE> op; void init () { vector<LINE> ().swap(op); } bool bad (LINE ln1, LINE ln2, LINE ln3) { __int128 hi = 1; return hi * (ln3.b - ln1.b) * (ln1.a - ln2.a) <= hi * (ln2.b - ln1.b) * (ln1.a - ln3.a); } void add (LINE ln) { while (op.size() >= 2 && bad(op[op.size() - 2], op[op.size() - 1], ln)) { op.pop_back(); } op.push_back(ln); } ar<int,2> get (int x) { if (op.empty()) return ar<int,2>{INF, -1l}; int lf = 0, rt = op.size() - 1; while (lf < rt) { int mid = (lf + rt) >> 1; if (op[mid](x) <= op[mid + 1](x)) rt = mid; else lf = mid + 1; } return ar<int,2>{op[lf](x), op[lf].id}; } }CHT; signed main() { int n, k; cin>>n>>k; int A[n]; for(int i = 0;i < n;i++)cin>>A[i]; int pref[n]; int prv[n][k]; pref[0] = A[0]; for(int i= 1;i < n;i++)pref[i] = pref[i - 1] + A[i]; int dp[n][k + 1]; for(int i = 0;i < n;i++)dp[i][0] = 0; for(int j = 1;j < k;j++){ CHT.init(); for(int i = 0;i < n;i++){ ar<int, 2> c = CHT.get(pref[i]); dp[i][j] = -c[0]; prv[j][i] = c[1]; CHT.add(LINE{-pref[i], -(dp[i][j - 1] - pref[i] * pref[i]), i}); } } for(int j = 1;j < k;j++){ for(int i = 1;i < n;i++){ //cout<<prv[j][i]<<" "; } //cout<<'\n'; } int res = -1; int opt = -1; for(int i = 0;i < n;i++){ if(res < dp[i][k - 1] + (pref[n - 1] - pref[i]) * pref[i]){ res = dp[i][k - 1] + (pref[n - 1] - pref[i]) * pref[i]; opt = i; } } cout<<res<<'\n'; vector<int> ans; for(int j = k - 1;j >= 0;j--){ ans.push_back(opt); opt = prv[j][opt]; } for(auto u:ans)cout<<u + 1<<" "; }
#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...