제출 #567704

#제출 시각아이디문제언어결과실행 시간메모리
567704ac2hu수열 (APIO14_sequence)C++14
22 / 100
101 ms131072 KiB
#include <bits/stdc++.h> #ifdef DEBUG #include "../templates/debug.h" #else #define deb(x...) #endif using namespace std; using ll = long long; constexpr ll sq(ll a){ return a*a; } struct Z{/*{{{*/ vector<ll> vals; int n; Z(vector<int> &a){ n = a.size(); vals.resize(n , 0); vals[0] = a[0]; for(int i = 1;i<n;i++){ vals[i] = vals[i - 1] + a[i]; } } ll operator()(int l,int r){ if(l > r)return 0; assert(n > r); assert(l <= r); assert(l >= 0); int temp = vals[r]; if(l != 0)temp -= vals[l - 1]; return temp; } };/*}}}*/ struct line{ ll m, c; int idx; ll get(ll x){ return m*x + c; } }; long double intersect(line a,line b){ return (long double)(a.c - b.c)/(a.m - b.m); } struct hull : deque<line>{ line get(ll x){ while(size() > 1 && back().get(x) <= at(size() - 2).get(x)) pop_back(); return back(); } void add(line nw){ while(size() >= 2 && intersect(at(0), at(1)) >= intersect(at(0), nw)) pop_front(); push_front(nw); } }; signed main(){ iostream::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int n, K;cin >> n >> K; vector<int> a(n); for(auto &e : a)cin >> e; Z pref(a); vector<vector<ll>> dp(n + 1, vector<ll>(K + 1, -1e17)); vector<vector<int>> jump(n + 1, vector<int>(K + 1, -1)); vector<hull> hulls(K + 10); dp[0][0] = 0; hulls[0].add({0, 0, 0}); for(int k = 1;k<=K;k++){ for(int i = 1;i<=n;i++){ if((int)hulls[k - 1].size() > 0){ line gg = hulls[k - 1].get(pref(i,n - 1)); dp[i][k] = pref.vals[i - 1]*pref(i,n - 1) + gg.get(pref(i, n - 1)); jump[i][k] = gg.idx; } if(i >= 2){ int m = 0; m = pref.vals[i - 2]; line nw = {-m, dp[i - 1][k], i - 1}; hulls[k].add(nw); } } } // for(int i = 0;i<=n;i++){ // deb(dp[i]); // } int MX = -1; ll val = -1; for(int i = 0;i<=n;i++){ if(dp[i][K] > val){ val = dp[i][K]; MX = i; } } cout << val << "\n"; vector<int> temp; int c = K; while(MX != 0 && MX != -1 && c > 0){ temp.push_back(MX); MX = jump[MX][c]; --c; } reverse(temp.begin(), temp.end()); for(int e : temp)cout << e << " "; cout << "\n"; }
#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...