제출 #240710

#제출 시각아이디문제언어결과실행 시간메모리
240710WhaleVomit수열 (APIO14_sequence)C++14
71 / 100
87 ms131076 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb push_back #define mp make_pair #define all(v) v.begin(), v.end() #define sz(v) (int)v.size() #define MOO(i, a, b) for(int i=a; i<b; i++) #define M00(i, a) for(int i=0; i<a; i++) #define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--) #define M00d(i,a) for(int i = (a)-1; i>=0; i--) #define FAST ios::sync_with_stdio(0); cin.tie(0); #define finish(x) return cout << x << '\n', 0; #define dbg(x) cerr << ">>> " << #x << " = " << x << "\n"; #define _ << " _ " << typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef pair<int,int> pi; typedef pair<ld,ld> pd; typedef complex<ld> cd; struct line { ll m; ll b; int idx; line(ll mm, ll bb, int idxp) { m = mm; b = bb; idx = idxp; } }; bool leftOf(line l1, line l2, line l3) { // is intersection of l1 and l3 to the left of l1 and l2? if(l2.m == l3.m) return 1; return (l3.b-l1.b)*(l1.m-l2.m) <= (l2.b-l1.b)*(l1.m-l3.m); } ll eval(ll x, line l) { return l.m * x + l.b; } bool better(ll x, line l1, line l2) { // l2(x) >= l1(x)? return eval(x, l2) >= eval(x, l1); } const int MAX_N = 100100; const int MAX_K = 202; int n, k; const ll inf = 1e17; ll arr[MAX_N]; ll psum[MAX_N]; ll dp[MAX_N][MAX_K]; int lastsplit[MAX_N][MAX_K]; int main() { FAST cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> arr[i]; psum[i] = psum[i-1] + arr[i]; } for(int j = 1; j <= k; j++) { for(int i = 0; i <= n; i++) { dp[i][j] = -inf; } } for(int j = 1; j <= k; j++) { deque<line> dq; dq.pb(line(psum[n],0,0)); for(int i = 1; i <= n; i++) { while(sz(dq) >= 2 && better(psum[i], dq[0], dq[1])) dq.pop_front(); dp[i][j] = -psum[i] * psum[i] + eval(psum[i], dq[0]); lastsplit[i][j] = dq[0].idx; line l3 = line(psum[n]+psum[i], dp[i][j-1]-psum[i]*psum[n],i); while(sz(dq) >= 2 && leftOf(dq[sz(dq)-2], dq[sz(dq)-1], l3)) dq.pop_back(); dq.pb(l3); } } int besIdx = 1; for(int i = 1; i <= n; i++) { if(dp[i][k] > dp[besIdx][k]) { besIdx = i; } } ll mx = dp[besIdx][k]; vi v; int cur = k; while(cur != 0) { v.pb(besIdx); besIdx = lastsplit[besIdx][cur]; cur--; } cout << mx << "\n"; M00(i, k) { if(i != 0) cout << " "; cout << v[i]; } 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...