QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#477193 | #9127. Optimal Train Operation | ucup-team3926# | WA | 0ms | 3660kb | C++20 | 6.3kb | 2024-07-13 23:59:57 | 2024-07-13 23:59:57 |
Judging History
answer
/*
author: Maksim1744
created: 13.07.2024 18:09:30
*/
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;}
template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U> p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun) fun
#define debugv(var) var
#define mclock void(0)
#define shows void(0)
#define debug if (false)
#define OSTREAM(...) ;
#define OSTREAM0(...) ;
#endif
const ll inf = 1e18;
ll intersect(pair<ll, ll> l1, pair<ll, ll> l2) {
if (l1.first < l2.first) swap(l1, l2);
// l1.first * x + l1.second = l2.first * x + l2.second
// x = (l2.second - l1.second) / (l1.first - l2.first)
// show(l1, l2);
ll num = l2.second - l1.second;
ll den = l1.first - l2.first;
assert(den > 0);
ll x;
if (num > 0)
x = num / den;
else
x = 0;
return x;
}
struct Segment {
deque<pair<ll, pair<ll, ll>>> lines;
void push_back(pair<ll, ll> line) {
if (lines.empty()) {
lines.eb(0, line);
return;
}
while (lines.size() >= 2 && lines.back().first >= intersect(lines[lines.size() - 2].second, line)) {
lines.pop_back();
}
lines.eb(intersect(lines.back().second, line), line);
if (lines.size() == 2 && lines[0].first == lines[1].first) lines.pop_front();
}
void push_front(pair<ll, ll> line) {
if (lines.empty()) {
lines.eb(0, line);
return;
}
while (lines.size() >= 2 && lines[0].first <= intersect(line, lines[1].second)) {
lines.pop_front();
}
lines.emplace_front(0, line);
lines[1].first = intersect(lines[0].second, lines[1].second);
// if (lines.size() == 2 && lines[0].first == lines[1].first) lines.pop_front();
}
int size() const {
return lines.size();
}
ll eval_at(ll x) const {
// int ind = lowb(lines, mp(x + 1, mp(-inf, -inf)));
// show(lines);
// show(x);
// show(ind);
// --ind;
// return lines[ind].second.first * x + lines[ind].second.second;
ll mn = inf;
for (const auto& [p, line] : lines)
mn = min(mn, line.first * x + line.second);
return mn;
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n;
cin >> n;
vector<ll> c(n);
vector<ll> a(n - 1);
cin >> c >> a;
a.insert(a.begin(), 0);
a.pb(0);
vector<Segment> segs;
segs.eb();
segs.back().push_back({0, 0});
vector<pair<ll, int>> st;
st.eb(0, 0);
auto merge_segs = [&](int i1, int i2) -> int {
if (i1 == -1) return i2;
if (i2 == -1) return i1;
show(segs[i1].lines, segs[i2].lines);
int res;
if (segs[i1].size() < segs[i2].size()) {
for (int i = (int)segs[i1].size() - 1; i >= 0; --i) {
segs[i2].push_front(segs[i1].lines[i].second);
}
res = i2;
} else {
for (int i = 0; i < segs[i2].size(); ++i) {
segs[i1].push_back(segs[i2].lines[i].second);
}
res = i1;
}
show(segs[res].lines);
return res;
};
// vector<pair<ll, pair<ll, ll>>> lines;
Segment glob;
glob.push_back({0, 0});
vector<ll> dp(n + 1);
show(c);
show(a);
for (int i = 1; i <= n; ++i) {
shows;
show(i, c[i - 1], a[i]);
show(glob.lines);
int i1 = -1;
while (!st.empty() && st.back().first <= c[i - 1]) {
i1 = merge_segs(st.back().second, i1);
st.pop_back();
}
while (!glob.lines.empty() && glob.lines.back().second.first <= c[i - 1])
glob.lines.pop_back();
show(glob.lines);
show(st);
if (i1 != -1) {
show(segs[i1].lines);
st.eb(c[i - 1], i1);
glob.push_back({c[i - 1], segs[i1].eval_at(c[i - 1])});
}
show(glob.lines);
show(glob.eval_at(i));
dp[i] = glob.eval_at(i) + a[i];
segs.eb();
segs.back().push_back({-i, dp[i]});
st.eb(0, segs.size() - 1);
}
show(dp);
cout << dp[n] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
4 3 1 4 1 5 9 2
output:
15
result:
ok "15"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3572kb
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: 3660kb
input:
7 476190629 262703497 211047202 971407775 628894325 731963982 822804784 877914575 602436426 24979445 861648772 623690081 433933447
output:
5339182432
result:
ok "5339182432"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3624kb
input:
8 910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016 430302156 982631932 161735902 880895728 923078537 707723857 189330739
output:
6311516364
result:
wrong answer 1st words differ - expected: '6166732840', found: '6311516364'