제출 #1058080

#제출 시각아이디문제언어결과실행 시간메모리
1058080codefox수열 (APIO14_sequence)C++14
71 / 100
59 ms131072 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") vector<vector<ll>> dp; vector<ll> pref; double inter2(int &i, int &j, int &k) { return ((-pref[j]*pref[j]+dp[j][k])-(-pref[i]*pref[i]+dp[i][k]))/(double)(pref[i]-pref[j]); } ll inter(int &i, int &j, int k) { return ((-pref[j]*pref[j]+dp[j][k])-(-pref[i]*pref[i]+dp[i][k])); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("../input.txt", "r", stdin); //freopen("../output.txt", "w", stdout); int n, k; cin >> n >> k; k++; vector<deque<int>> ch(k+1); ch[0].push_back(0); pref.assign(n+1, 0); dp.assign(n+1, vector<ll>(k+1, 0)); vector<vector<int>> best(n+1, vector<int>(k+1, -1)); for (int i = 1; i <= n; i++) { int a; cin >> a; pref[i] = pref[i-1]; pref[i]+=a; for(int j = min(k-1, i-1); j>= 0; j--) { while (ch[j].size()>1 && inter2(ch[j][0], ch[j][1], j)<= pref[i]) ch[j].pop_front(); int h = ch[j].front(); best[i][j+1] = h; dp[i][j+1] = dp[h][j]-pref[h]*(pref[h]-pref[i]); while (ch[j+1].size()>1 && inter(ch[j+1][ch[j+1].size()-2], ch[j+1].back(), j+1) *(pref[ch[j+1].back()]-pref[i]) >= inter(ch[j+1].back(), i, j+1) *(pref[ch[j+1][ch[j+1].size()-2]]-pref[ch[j+1].back()])) ch[j+1].pop_back(); ch[j+1].push_back(i); } } int cn = n; cout << dp[cn][k] << "\n"; for (int i = k; i >= 2; i--) { cout << best[cn][i] << " "; cn = best[cn][i]; } return 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...