이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array
const int LOG = 20;
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 3005;
namespace CHT{
struct Line{
__int128_t a, b, id;
int operator()(int x){
return a * x + b;
}
};
bool bad(Line l1, Line l2, Line l3){
return (l3.b - l1.b) * (l1.a - l2.a) <= (l2.b - l1.b) * (l1.a - l3.a);
}
vector<Line> h;
void init(){
h = vector<Line>();
}
void insert(Line l){
while(h.size() >= 2 && bad(h[h.size() - 2], h[h.size() - 1], l))h.pop_back();
h.push_back(l);
}
ar<int, 2> qry(int x){
if(h.empty())return {INF, 0};
int lo = 0, hi = h.size() - 1;
while(lo < hi){
int m = (lo + hi) / 2;
if(h[m](x) <= h[m + 1](x))hi = m;
else lo = m + 1;
}
return {h[lo](x), h[lo].id};
}
};
signed main() {
int n, k;
cin>>n>>k;
int A[n];
for(int i = 0;i < n;i++)cin>>A[i];
int pref[n];
int prv[n][k + 1];
pref[0] = A[0];
for(int i= 1;i < n;i++)pref[i] = pref[i - 1] + A[i];
int dp[n][k + 1];
for(int i = 0;i < n;i++)dp[i][0] = 0;
for(int j = 1;j < k;j++){
CHT::init();
for(int i = 0;i < n;i++){
ar<int, 2> c = CHT::qry(pref[i]);
dp[i][j] = -c[0];
prv[j][i] = c[1];
CHT::insert(CHT::Line{-pref[i], -(dp[i][j - 1] - pref[i] * pref[i]), i});
}
}
int res = -1;
int opt = -1;
for(int i = 0;i < n;i++){
if(res < dp[i][k - 1] + (pref[n - 1] - pref[i]) * pref[i]){
res = dp[i][k - 1] + (pref[n - 1] - pref[i]) * pref[i];
opt = i;
}
}
cout<<res<<'\n';
vector<int> ans;
for(int j = k - 1;j >= 0;j--){
ans.push_back(opt);
opt = prv[j][opt];
}
for(auto u:ans)cout<<u + 1<<" ";
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'std::array<long long int, 2> CHT::qry(long long int)':
sequence.cpp:42:33: warning: narrowing conversion of 'CHT::h.std::vector<CHT::Line>::operator[](((std::vector<CHT::Line>::size_type)lo)).CHT::Line::id' from '__int128' to 'long long int' [-Wnarrowing]
42 | return {h[lo](x), h[lo].id};
# | 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... |