이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;using f64 = double;using i64=long long;using u64=unsigned long long;
template<typename T> using Arr=vector<T>;
#define hfor(v, s, e) for(int v=(s);(s)<=v&&v<(e);++v)//half-opened range
#define hfori(v, s, e) for(int v=(e)-1;(s)<=v&&v<(e);--v)//inversion
#define hforo(v, s, e) int v=(s);for(;(s)<=v&&v<(e);++v)//out declaration
#define hforoi(v, s, e) int v=(e)-1; for(;(s)<=v&&v<(e);--v)
#define cfor(v, s, e) hfor(v,(s),(e)+1)//closed range
#define cfori(v, s, e) hfori(v,(s),(e)+1)
#define cforo(v, s, e) hforo(v,(s),(e)+1)
#define cforoi(v, s, e) hforoi(v,(s),(e)+1)
#define rep(v,x) hfor(v,0,(x))
#define repi(v,x) hfori(v,0,(x))
#define repo(v,x) hforo(v,0,(x))
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define empl emplace
#define emplb emplace_back
#define emplf emplace_front
#define fi first
#define se second
#define cxp constexpr
#define PQ std::priority_queue
#ifndef DEBUG
#pragma GCC optimize ("Ofast")
auto __PRE_RUN__=(ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),(cout<<fixed<<setprecision(11)), 0);
#endif
template<typename T> cxp T inf() { return numeric_limits<T>::max() / 2; }
auto mapf(auto a, auto f){for(auto& x:a)x=f(x); return a;}
int rd(int lb, int ub){static mt19937 rng(time(0)^i64(new int)); return uniform_int_distribution<int>(lb, ub-1)(rng);}
int rd(int ub=inf<int>()){return rd(0,ub);}
const f64 pi=acosl(-1);
template<typename T>
struct Xarr: public Arr<T>{
Xarr(int n=0, const T& init=T(), int offset=1):Arr<T>(n+offset, init), o(offset){}
T& operator[](int i){return at(i);}
T& at(int i){return Arr<T>::at(i+o);}
const T& operator[](int i)const{return at(i);}
const T& at(int i)const{return Arr<T>::at(i+o);}
int o;
};
#define endl '\n'//not interactive?
#define int i64//MLE?
using pint = pair<int,int>;
using tint = tuple<int,int,int>;
struct Line{
int tan, yic;
f64 lx=-1/0.0, rx=1/0.0;
int idx=0;
bool operator<(const Line& r)const{return tan<r.tan;}
bool operator<(const i64 x)const{return rx<x;}
f64 intersectX(const Line& r)const{return (r.yic-yic)/f64(tan-r.tan);}
int f(int x)const{return tan*x+yic;}
};
struct StackCHT{
Arr<Line> st;
int idx=0;
void push(i64 tan, i64 yic){
Line f{tan, yic, 0, 1/0.0,idx++};
while(sz(st)){
f.lx=st.back().intersectX(f);
if(tan==st.back().tan || f.lx<st.back().lx)
st.popb();
else
break;
}
st.pushb(f);
}
int i=0;
i64 get(i64 x){
while(i<sz(st) and st[i].lx<=x)
i++;
return st[i-1].tan*x+st[i-1].yic;
//int s=0, e=sz(st);
//while(e-s>1){
// int m=(s+e)/2;
// (x<st[m].lx?e:s)=m;
//}
//return st[s].tan*x + st[s].yic;
}
};
Xarr<int> p(100000);
int dp[2][100000];
signed sav[201][100000];
void bt(int k, int i){
if(!k)
return;
bt(k-1,sav[k][i]);
cout<<sav[k][i]+1<<' ';
}
signed main(){
int n,k; cin>>n>>k;
int a[n];
rep(i,n)
cin>>a[i];
rep(i,n)
p[i]=p[i-1]+a[i];
cfor(i,1,k){
StackCHT s;
s.push(p[0], -p[0]*p[0]+0);
hfor(j,1,n){
dp[i%2][j]=s.get(p[j]);
s.push(p[j], -p[j]*p[j]+dp[(i+1)%2][j]);
sav[i][j]=s.st[s.i-1].idx;
}
}
cout<<dp[k%2][n-1]<<endl;
bt(k,n-1);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |