QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#763600 | #9127. Optimal Train Operation | ghijk | WA | 2ms | 11872kb | C++20 | 3.9kb | 2024-11-19 21:08:43 | 2024-11-19 21:08:44 |
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 = 1e18;
#define int long long
int n, a[MAXN], c[MAXN];
ll dp[MAXN], mx;
struct point {
ll x, y;
ll dot(point p) {
return x * p.x + y * p.y;
}
ll cross(point p) {
return x * p.y - y * p.x;
}
point conj() {
return {-y, x};
}
point vt(point p) {
return {x - p.x, y - p.y};
}
};
vector<point> hull, vec;
void add(ll a, ll b) {
auto p = point{a, b};
while (vec.size() >= 1 && vec.back().dot(p.vt(hull.back())) >= 0) { // <= 0 neu max
vec.pop_back();
hull.pop_back();
}
if (!hull.empty())
vec.push_back(p.vt(hull.back()).conj());
hull.push_back(p);
}
ll get(ll x) {
if(hull.empty()) return oo;
auto query = point{x, 1};
auto it = lower_bound(vec.begin(), vec.end(), query, [](point a, point b) {
return a.cross(b) > 0; // <0 neu max
});
return query.dot(hull[it - vec.begin()]);
}
void clear(){
hull.clear();
vec.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();
mx = 0;
for (int i = mid + 1, j = mid + 1; i <= r; ++i){
while (j > l && suf[j - 1] <= pre[i]) {
--j;
add(j, dp[j]);
}
minimize(dp[i], get(-pre[i]) + 1ll * i * pre[i] + a[i]);
}
clear();
mx = 0;
for (int i = r, j = l - 1; i > mid; --i){
while (j < mid && suf[j + 1] >= pre[i]){
++j;
add(suf[j], dp[j] - 1ll * j * suf[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 + 1, 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: 100
Accepted
time: 0ms
memory: 11868kb
input:
4 3 1 4 1 5 9 2
output:
15
result:
ok "15"
Test #2:
score: 0
Accepted
time: 2ms
memory: 11796kb
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: 2ms
memory: 11864kb
input:
7 476190629 262703497 211047202 971407775 628894325 731963982 822804784 877914575 602436426 24979445 861648772 623690081 433933447
output:
5339182432
result:
ok "5339182432"
Test #4:
score: 0
Accepted
time: 0ms
memory: 11840kb
input:
8 910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016 430302156 982631932 161735902 880895728 923078537 707723857 189330739
output:
6166732840
result:
ok "6166732840"
Test #5:
score: 0
Accepted
time: 0ms
memory: 11844kb
input:
5 191890310 576823355 782177068 404011431 818008580 839296263 462224593 492601449 384836991
output:
4069897043
result:
ok "4069897043"
Test #6:
score: 0
Accepted
time: 1ms
memory: 11872kb
input:
6 138996221 501899080 353195922 545531545 910748511 350034067 160449218 155374934 840594328 164163676 797829355
output:
3921700772
result:
ok "3921700772"
Test #7:
score: 0
Accepted
time: 1ms
memory: 11800kb
input:
2 824284691 533206504 470338674
output:
1648569382
result:
ok "1648569382"
Test #8:
score: -100
Wrong Answer
time: 2ms
memory: 11868kb
input:
4524 43 144 216 44 156 252 243 172 78 246 56 103 207 177 102 22 202 236 61 255 128 238 237 187 176 110 156 213 65 11 75 239 142 9 203 124 154 149 119 59 152 91 151 226 131 184 174 236 220 149 16 209 51 32 40 131 119 138 201 171 249 150 108 82 75 70 204 80 131 42 180 125 257 131 5 107 39 145 154 242 ...
output:
894175
result:
wrong answer 1st words differ - expected: '892773', found: '894175'