이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int N_MAX = 1e5;
struct defLine {
int64 slope, h; int index;
int64 getEval (int64 t) {return slope * t + h;}
bool getIn (defLine first, defLine second) {
int64 LHS = (h - first.h) * (second.slope - first.slope);
int64 RHS = (first.slope - slope) * (first.h - second.h);
return LHS <= RHS;
}
long double intersectX (defLine aux) {return (long double)(aux.h - h) / (slope - aux.slope);}
};
deque<defLine> CHT;
void push (defLine newLine) {
while (CHT.size () >= 2 && newLine.getIn (CHT[CHT.size () - 2], CHT[CHT.size () - 1]))
CHT.pop_back ();
CHT.push_back (newLine);
}
const int NONE = -1;
const int64 INF = 1e18;
defLine query (int64 target) {
if (CHT.size () == 0)
return {0, -INF, NONE};
while (CHT.size () >= 2 && CHT[0].getEval (target) <= CHT[1].getEval (target))
CHT.pop_front ();
return CHT[0];
}
int n, k; int64 input[1 + N_MAX], pSum[1 + N_MAX];
void initInput (void) {
cin >> n >> k;
for (int i = 1; i <= n; i ++)
cin >> input[i];
for (int i = 1; i <= n; i ++)
pSum[i] = pSum[i - 1] + input[i];
}
const int K_MAX = 200;
int pointTo[1 + K_MAX][1 + N_MAX];
int64 DP[1 + N_MAX], prevDP[1 + N_MAX];
void solve (void) {
for (int t = 1; t <= k; t ++) {
for (int i = 1; i <= t; i ++) {
DP[i] = -INF;
defLine line = {pSum[i], prevDP[i] - pSum[i] * pSum[i], i};
push (line);
}
for (int i = t + 1; i <= n; i ++) {
defLine bestLine = query (pSum[i]);
pointTo[t][i] = bestLine.index;
DP[i] = bestLine.getEval (pSum[i]);
///if (t == 1 && i == 3)
/// cout << DP[i] << "\n";
defLine newLine = {pSum[i], prevDP[i] - pSum[i] * pSum[i], i};
push (newLine);
}
CHT.clear ();
for (int i = 1; i <= n; i ++)
prevDP[i] = DP[i];
}
cout << DP[n] << "\n";
int t = k, p = n;
while (t > 0) {
cout << pointTo[t][p] << " ";
p = pointTo[t][p], t --;
}
}
int main()
{
initInput ();
solve ();
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... |