이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int MAX = 1e5 + 5;
namespace CH {
struct rect {
int64 n, m;
int id;
rect() {}
rect(int64 n, int64 m, int id) : n(n), m(m), id(id) {}
int64 eval(int64 x) {
return m * x + n;
}
};
int k, opt;
rect stk[MAX];
void init() {
k = 0, opt = 1;
}
bool bad_line(rect l1, rect l2, rect l3) {
return (l1.n - l3.n) * (l2.m - l1.m) < (l3.m - l1.m) * (l1.n - l2.n);
}
void add(rect r) {
while(k > 1 && bad_line(stk[k - 1], stk[k], r))
k--;
stk[++k] = r;
}
pair <int64, int> query(int64 x) {
if(k == 0)
return { -1, -1 };
if(opt > k)
opt = k;
while(opt < k && stk[opt].eval(x) <= stk[opt + 1].eval(x))
opt++;
return { stk[opt].eval(x), stk[opt].id };
}
}
int n, k;
pair <int, int> p[MAX][205];
int64 t[MAX], dp[MAX][205];
vector <int64> ans;
int main() {
scanf("%d%d", &n, &k);
k++;
for(int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
t[i] = t[i - 1] + x;
}
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
for(int l = 1; l <= k; l++) {
CH::init();
for(int i = 1; i <= n; i++) {
if(dp[i - 1][l - 1] != -1)
CH::add(CH::rect(dp[i - 1][l - 1] - t[i - 1] * t[i - 1], t[i - 1], i - 1));
auto o = CH::query(2LL * t[i] - t[n]);
dp[i][l] = o.first;
if(dp[i][l] != -1) {
dp[i][l] += t[i] * t[n] - t[i] * t[i];
p[i][l] = { o.second, l - 1 };
}
}
}
/*printf("%lld\n", dp[n][k] / 2);
int x = n, y = k;
while(1) {
if(x == 0)
break;
ans.push_back(x);
int nx = p[x][y].first;
int ny = p[x][y].second;
x = nx, y = ny;
}
reverse(ans.begin(), ans.end());
ans.pop_back();
for(int i = 0; i < (int) ans.size(); i++) {
printf("%lld", ans[i]);
printf(i == (int) ans.size() - 1 ? "\n" : " ");
}*/
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'int main()':
sequence.cpp:58:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &k);
^
sequence.cpp:63:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x; scanf("%d", &x);
^
# | 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... |