이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define int long long
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
int n, a[N], dp[N];
struct Line{
int m, c;
int val(int x){
return m*x + c;
}
};
vector<pair<vector<Line>, int> > hulls;
vector<Line> merge(vector<Line> a, vector<Line> b){
// a and b is already sorted in increasing order of slopes
vector<Line> ans;
int i = 0, j = 0;
while(i < a.size() and j < b.size()){
if(a[i].m >= b[j].m){
ans.pb(a[i]);
++i;
}
else{
ans.pb(b[j]);
++j;
}
}
while(i < a.size()){
ans.pb(a[i]);
++i;
}
while(j < b.size()){
ans.pb(b[j]);
++j;
}
return ans;
}
bool check(Line a, Line b, Line c) {
// do a and c cover b?
long long left = (b.c - a.c);
left = left * (b.m - c.m);
long long right = (c.c - b.c);
right = right * (a.m - b.m);
return left > right;
}
bool cmp(Line a, Line b){
if(a.m == b.m)
return a.c < b.c;
return a.m > b.m;
}
vector<Line> CHT(vector<Line> cur){
sort(cur.begin(), cur.end(), cmp);
vector<Line> temp;
temp.pb(cur[0]);
for(int i = 1; i < cur.size(); ++i){
if(cur[i].m == temp.back().m)
continue;
temp.pb(cur[i]);
}
cur = temp;
vector<Line> hull;
hull.pb(cur[0]); // first line will always be in the hull
if(cur.size() == 1)
return hull;
hull.pb(cur[1]); // assuming this line is also in the hull
for(int j = 2; j < cur.size(); ++j){
while(hull.size() > 1){
Line pre = hull.back(), par = hull[hull.size() - 2];
if(check(par, pre, cur[j]))
hull.pop_back();
else
break;
}
hull.pb(cur[j]);
}
return hull;
}
void addLine(Line a){
vector<Line> cur;
cur.pb(a);
hulls.pb({cur, 1});
// you should merge last two if both are same size
while(hulls.size() > 1){
vector<Line> cur = hulls[hulls.size() - 1].F, pre = hulls[hulls.size() - 2].F;
if(hulls[hulls.size() - 1].S == hulls[hulls.size() - 2].S){
// merge these two hulls into one
vector<Line> ans;
ans = CHT(merge(pre, cur));
int x = hulls[hulls.size() - 1].S + hulls[hulls.size() - 2].S;
hulls.pop_back();
hulls.pop_back();
hulls.push_back({ans, x});
}
else
break;
}
}
int get(int x){
int res = LLONG_MAX;
for(int j = 0; j < hulls.size(); ++j){
int low = 0, high = (int) hulls[j].F.size() - 2, ans = (int) hulls[j].F.size() - 1;
while(low <= high){
int mid = (low + high) / 2;
if(hulls[j].F[mid].val(x) <= hulls[j].F[mid + 1].val(x)){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
res = min(res, hulls[j].F[ans].val(x));
}
return res;
}
void solve(){
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i];
for(int i = 1; i <= n; ++i){
Line cur;
cur.m = n - i + 1, cur.c = dp[i - 1];
addLine(cur);
dp[i] = get(a[i]);
}
cout << dp[n] << "\n";
}
int32_t main(){
fast;
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Discharging.cpp: In function 'std::vector<Line> merge(std::vector<Line>, std::vector<Line>)':
Discharging.cpp:25:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | while(i < a.size() and j < b.size()){
| ~~^~~~~~~~~~
Discharging.cpp:25:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | while(i < a.size() and j < b.size()){
| ~~^~~~~~~~~~
Discharging.cpp:35:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | while(i < a.size()){
| ~~^~~~~~~~~~
Discharging.cpp:39:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while(j < b.size()){
| ~~^~~~~~~~~~
Discharging.cpp: In function 'std::vector<Line> CHT(std::vector<Line>)':
Discharging.cpp:65:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i = 1; i < cur.size(); ++i){
| ~~^~~~~~~~~~~~
Discharging.cpp:76:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int j = 2; j < cur.size(); ++j){
| ~~^~~~~~~~~~~~
Discharging.cpp: In function 'long long int get(long long int)':
Discharging.cpp:112:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::vector<Line>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int j = 0; j < hulls.size(); ++j){
| ~~^~~~~~~~~~~~~~
# | 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... |