QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#506657 | #9127. Optimal Train Operation | hos_lyric | RE | 0ms | 3856kb | C++14 | 4.2kb | 2024-08-05 20:30:20 | 2024-08-05 20:30:21 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
constexpr Int INF = 1001001001001001001LL;
/*
min
slope: decr.
eval at: decr.
*/
struct Cht {
vector<pair<Int, Int>> stack;
Cht() {
// cerr<<"[Cht]"<<endl;
}
~Cht() {
// cerr<<"[~Cht]"<<endl;
}
void add(Int p, Int q) {
// cerr<<" [add] "<<p<<" "<<q<<endl;
if (stack.size() >= 1) assert(stack.back().first >= p);
stack.emplace_back(p,q);return;
if (stack.size() >= 1 && stack.back().first == p) {
if (stack.back().second <= q) {
return;
} else {
stack.pop_back();
}
}
for (; stack.size() >= 2; ) {
const Int p2 = stack.end()[-2].first, q2 = stack.end()[-2].second;
const Int p1 = stack.end()[-1].first, q1 = stack.end()[-1].second;
// (q1 - q2) / (p2 - p1) < (q - q1) / (p1 - p)
if ((q1 - q2) * (p1 - p) < (q - q1) * (p2 - p1)) {
break;
} else {
stack.pop_back();
}
}
stack.emplace_back(p, q);
}
Int get(Int x) {
// cerr<<" [get] "<<x<<endl;
Int mn=INF;for(const auto&l:stack)chmin(mn,l.first*x+l.second);return mn;
for (; stack.size() >= 2; ) {
const Int p2 = stack.end()[-2].first, q2 = stack.end()[-2].second;
const Int p1 = stack.end()[-1].first, q1 = stack.end()[-1].second;
if (p2 * x + q2 > p1 * x + q1) {
break;
} else {
stack.pop_back();
}
}
return stack.size() ? (stack.back().first * x + stack.back().second) : INF;
}
};
int N;
vector<Int> C, A;
vector<Int> dp;
void rec(int l, int r) {
if (l + 1 == r) {
chmin(dp[r], dp[l] + A[l] + C[l]);
} else {
const int m = (l + r) / 2;
rec(l, m);
// [l, m) -> (m, r]
// max in left
{
Int c = 0;
vector<vector<pair<Int, Int>>> liness(r - m + 1);
for (int i = m, j = m; --i >= l; ) {
chmax(c, C[i]);
for (; j < r && c >= C[j]; ++j) {}
// dp[i] + A[i] + c (j - i)
liness[j - m].emplace_back(c, dp[i] + A[i] - c * i);
}
Cht cht;
for (int j = r; j > m; --j) {
for (const auto &line : liness[j - m]) cht.add(line.first, line.second);
const Int res = cht.get(j);
chmin(dp[j], res);
}
}
// max in right
{
Int c = 0;
Cht cht;
for (int i = m, j = m; ++j <= r; ) {
chmax(c, C[j - 1]);
for (; i > l && C[i - 1] <= c; ) {
--i;
// dp[i] + A[i] + c (j - i)
cht.add(i, dp[i] + A[i]);
}
const Int res = cht.get(-c);
chmin(dp[j], res + c * j);
}
}
rec(m, r);
}
}
int main() {
for (; ~scanf("%d", &N); ) {
C.resize(N);
for (int i = 0; i < N; ++i) scanf("%lld", &C[i]);
A.assign(N + 1, 0);
for (int i = 1; i < N; ++i) scanf("%lld", &A[i]);
// reverse(C.begin(),C.end());
// reverse(A.begin(),A.end());
dp.assign(N + 1, INF);
dp[0] = 0;
rec(0, N);
// cerr<<"dp = "<<dp<<endl;
printf("%lld\n", dp[N]);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
input:
4 3 1 4 1 5 9 2
output:
15
result:
ok "15"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
9 28 35 19 27 84 98 78 79 60 40 35 54 63 72 71 27 94
output:
682
result:
ok "682"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
7 476190629 262703497 211047202 971407775 628894325 731963982 822804784 877914575 602436426 24979445 861648772 623690081 433933447
output:
5339182432
result:
ok "5339182432"
Test #4:
score: -100
Runtime Error
input:
8 910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016 430302156 982631932 161735902 880895728 923078537 707723857 189330739