QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#763661 | #9127. Optimal Train Operation | ghijk | WA | 2ms | 11932kb | C++20 | 3.7kb | 2024-11-19 21:32:14 | 2024-11-19 21:32:15 |
Judging History
answer
// author : anhtun_hi , nqg
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define reset(h, v) memset(h, v, sizeof h)
#define Forv(i, a) for(auto& i : a)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define c_bit(i) __builtin_popcountll(i)
#define Bit(mask, i) ((mask >> i) & 1LL)
#define onbit(mask, i) ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
using namespace std;
namespace std {
template <typename T, int D>
struct _vector : public vector <_vector <T, D - 1>> {
static_assert(D >= 1, "Dimension must be positive!");
template <typename... Args>
_vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
};
template <typename T> struct _vector <T, 1> : public vector <T> {
_vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
};
template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;}
template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;}
}
const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5;
const int MAXN = 1e6 + 5;
const ll mod = 1e9 + 7;
const ll oo = 1e15;
#define int long long
int n, a[MAXN], c[MAXN];
ll dp[MAXN], mx;
struct Line {
long long a, b;
Line(long long a = 0, long long b = oo): a(a), b(b) {}
long long eval(long long x) { return a * x + b; }
};
vector <Line> lines; int ptr;
bool bad(Line a, Line b, Line c) { return (long double) (c.b - a.b) / (a.a - c.a) < (long double) (b.b - a.b) / (a.a - b.a); }
void add(long long a, long long b) {
Line l(a, b);
while (lines.size() >= 2 && bad(lines.end()[-2], lines.back(), l)) lines.pop_back();
lines.push_back(l);
}
ll get(long long x) {
if (ptr >= (int) lines.size()) ptr = (int) lines.size() - 1;
while (ptr < (int) lines.size() - 1 && lines[ptr].eval(x) > lines[ptr + 1].eval(x)) ++ptr;
return lines[ptr].a * x + lines[ptr].b ;
}
void clear(){
lines.clear();
}
int pre[MAXN], suf[MAXN];
void solve(int l, int r)
{
if (l == r) return;
int mid = l + r >> 1;
solve(l, mid);
pre[mid] = 0; For(i, mid + 1, r) pre[i] = max(pre[i - 1], c[i]);
suf[mid] = 0; Ford(i, mid - 1, l) suf[i] = max(suf[i + 1], c[i + 1]);
clear();
for (int i = mid + 1, j = mid; i <= r; ++i){
while (j >= l && suf[j] <= pre[i]) {
add(j, dp[j]);
--j;
}
minimize(dp[i], get(-pre[i]) + 1ll * i * pre[i] + a[i]);
}
clear();
for (int i = r, j = l; i > mid; --i){
while (j <= mid && suf[j] >= pre[i]){
add(suf[j], (dp[j] - 1ll * j * suf[j]));
++j;
}
minimize(dp[i], get(i) + a[i]);
}
solve(mid + 1, r);
}
void Solve() {
cin >> n;
For(i, 1, n) cin >> c[i];
For(i, 1, n - 1) cin >> a[i];
fill(dp, dp + n + 5, oo);
dp[0] = 0;
// For(i, 1, n){
// ll ma = 0;
// Ford(j, i - 1, 0){
// maximize(ma, c[j]);
// minimize(dp[i], dp[j] + (i - j) * ma + a[i]);
// }
// }
solve(0, n);
cout << dp[n] << '\n';
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
if(fopen("a.inp", "r")) {
freopen("a.inp", "r", stdin);
freopen("a.out", "w", stdout);
}
int t = 1;
// cin >> t;
while(t --) Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 11932kb
input:
4 3 1 4 1 5 9 2
output:
-140304673890093
result:
wrong answer 1st words differ - expected: '15', found: '-140304673890093'