이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3,fast-math")
const int N = 1e5+1;
const int K = 202;
ll dp[N][2];
ll pref[N];
int best[N][K];
double inter2(int &i, int &j)
{
return ((-pref[j]*pref[j]+dp[j][0])-(-pref[i]*pref[i]+dp[i][0]))/(double)(pref[i]-pref[j]);
}
ll inter(int &i, int &j)
{
return ((-pref[j]*pref[j]+dp[j][1])-(-pref[i]*pref[i]+dp[i][1]));
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("../input.txt", "r", stdin);
//freopen("../output.txt", "w", stdout);
int n, k;
cin >> n >> k;
k++;
deque<int> ch[K];
ch[0].push_back(0);
pref[0] = 0;
dp[0][0] =0;
vector<int> as(n+1);
for (int i = 1; i <= n; i++)
{
cin >> as[i];
pref[i] = pref[i-1];
pref[i]+=as[i];
}
for (int j = 0; j < k; j++)
{
for (int i = j; i <= n; i++)
{
while (ch[j].size()>1 && inter2(ch[j][0], ch[j][1])<=
pref[i]) ch[j].pop_front();
int h = ch[j].front();
best[i][j+1] = h;
dp[i][1] = dp[h][0]-pref[h]*(pref[h]-pref[i]);
while (ch[j+1].size()>1 &&
inter(ch[j+1][ch[j+1].size()-2], ch[j+1].back())
*(pref[ch[j+1].back()]-pref[i]) >=
inter(ch[j+1].back(), i)
*(pref[ch[j+1][ch[j+1].size()-2]]-pref[ch[j+1].back()]))
ch[j+1].pop_back();
ch[j+1].push_back(i);
}
for (int i = 1; i <= n; i++)
{
dp[i][0] = dp[i][1];
}
}
int cn = n;
cout << dp[cn][0] << "\n";
for (int i = k; i >= 2; i--)
{
cout << best[cn][i] << " ";
cn = best[cn][i];
}
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... |