제출 #1088253

#제출 시각아이디문제언어결과실행 시간메모리
1088253Nurislam수열 (APIO14_sequence)C++17
0 / 100
20 ms12228 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ff first #define ss second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define int long long template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } const int N = 1e6+50, inf = 1e17; //int mod = 998244353 //int mod = 1000000007; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rnd(l, r) uniform_int_distribution <int> (l, r)(rng) struct line{ int m, c, i; line(int _m,int _c, int _i) : m(_m), c(_c), i(_i){ }; int calc(int x){ return m * x + c; }; long double xnt(line & other){ return (long double)(c - other.c)/(m - other.m); }; }; void solve(){ int n, k; cin >> n >> k; vector<int> v(n+1); for(int i = 1; i<= n; i++){cin >> v[i];v[i] += v[i-1];} vector<vector<int>> dp(2, vector<int> (n+2)); vector<vector<int>> from(n+2, vector<int> (k+2)); for(int j = 1; j <= k; j++){ //cout << 1 << '\n'; deque<line> dq; dq.pb({0,0,0}); for(int i = 1; i <= n; i++){ int ps = v[n] - v[i]; while(dq.size() > 1 && dq.back().calc(ps) <= dq[dq.size()-2].calc(ps)){ dq.pop_back(); } dp[1][i] = dq.back().calc(ps) + v[i] * ps; from[i][j] = dq.back().i; line nw = {-v[i], dp[0][i], i}; while(dq.size() > 1 && nw.xnt(dq[0]) > dq[0].xnt(dq[1])){ dq.pop_front(); } dq.push_front(nw); } dp[0] = dp[1]; } pair<int,int> ans = {-1, 0}; for(int i = 1; i <= n; i++){ ans = max(ans, {dp[0][i], i}); } cout << ans.ff << '\n'; vector<int> ind; for(int i = k, idx = ans.ss; i >= 1; i--){ ind.pb(idx); idx = from[idx][i]; } reverse(all(ind)); for(int i:ind)cout << i << " "; cout << "\n"; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int tt = 1; //cin >> tt; while(tt--){ 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...