제출 #1223200

#제출 시각아이디문제언어결과실행 시간메모리
1223200Szymon_PilipczukSplit the sequence (APIO14_sequence)C++20
71 / 100
858 ms166280 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define int long long #define st first #define nd second #define pb push_back #define all(a) a.begin(),a.end() #define rep(a,b) for(int a = 0;a<b;a++) const int inf = 1e9; const ll infl = 1e18; int n,k; ll sq(ll a) { return a*a; } deque<vector<ll>> dq; void add(ll a,ll b,int i) { if(dq.size() == 0) { dq.push_back({0,infl,a,b,i}); return; } vector<ll> c = dq.back(); if(c[2] == a) { if(c[3] > b) { dq.pop_back(); add(a,b,i); } } else { ll cu = (b-c[3])/(c[2]-a) + 1; if(cu <= c[0]) { dq.pop_back(); add(a,b,i); } else { dq.back()[1] = cu-1; dq.pb({cu,infl,a,b,i}); } } } pair<ll,ll> check(ll c) { while(dq.front()[1] < c) { dq.pop_front(); } return {c * dq.front()[2] + dq.front()[3],dq.front()[4]}; } ll pref[100000]; vector<int> ord; int p[200][99999]; ll c[99999][2]; ll solve() { rep(q,k) { rep(i,n-1) { c[i][0] = c[i][1]; } dq.clear(); add(0,inf,-1); if(q == 0) { add(0,0,-1); } rep(i,n-1) { p[q][i] = check(pref[i]).nd; c[i][1] = check(pref[i]).st; if(q != 0) add(-2 * pref[i],c[i][0] + sq(pref[i])*2,i); } } dq.clear(); rep(i,n-1) { add(-2 * pref[i],c[i][1] + sq(pref[i])*2,i); } int ci = check(pref[n-1]).nd; int cu = k-1; while(ci != -1) { ord.pb(ci); ci = p[cu][ci]; cu--; } reverse(all(ord)); return check(pref[n-1]).st + pref[n-1]*pref[n-1]; } int32_t main() { cin>>n>>k; int cu; cin>>cu; pref[0] = cu; rep(i,n-1) { int c; cin>>c; pref[i+1] = pref[i]+c; } ll ans = solve(); cout<<(sq(pref[n-1])-ans)/2<<"\n"; rep(i,k) { cout<<ord[i]+1<<" "; } 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...