QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#731660 | #9127. Optimal Train Operation | cpismylifeOwO | WA | 2ms | 11908kb | C++20 | 3.4kb | 2024-11-10 10:19:01 | 2024-11-10 10:19:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
int n;
int arr[MaxN];
int c[MaxN];
void Inp()
{
cin >> n;
for (int x = 1; x <= n; x++)
{
cin >> c[x];
}
for (int x = 1; x < n; x++)
{
cin >> arr[x];
}
arr[n] = 0;
}
struct Line
{
long long a, b;
Line() = default;
Line(long long _a, long long _b)
{
a = _a;
b = _b;
}
};
bool Check(const Line& a, const Line& b, const Line& c)
{
return (long double)(a.b - b.b) / (b.a - a.a) < (long double)(a.b - c.b) / (c.a - a.a);
}
vector<Line> hull;
vector<long double> intersect;
void Reset()
{
hull.clear();
intersect.clear();
}
void Add(const Line& k)
{
if (!hull.empty() && hull.back().a == k.a)
{
if (hull.back().b > k.b)
{
hull.pop_back();
intersect.pop_back();
if (!hull.empty())
{
intersect.pop_back();
intersect.push_back((long double)(hull.back().b - k.b) / (k.a - hull.back().a));
}
hull.push_back(k);
intersect.push_back(1e18);
}
return;
}
while ((int)hull.size() > 1)
{
Line p = hull.back();
hull.pop_back();
if (Check(hull.back(), p, k))
{
hull.push_back(p);
break;
}
intersect.pop_back();
}
if (!hull.empty())
{
intersect.pop_back();
intersect.push_back((long double)(hull.back().b - k.b) / (k.a - hull.back().a));
}
hull.push_back(k);
intersect.push_back(1e18);
}
long long Query(long long x)
{
if (hull.empty())
{
return inf;
}
int p = upper_bound(intersect.begin(), intersect.end(), (long double)x) - intersect.begin();
return hull[p].a * x + hull[p].b;
}
int premx[MaxN];
int sufmx[MaxN];
long long F[MaxN];
void DNC(int l, int r)
{
if (l == r)
{
return;
}
int mid = (l + r) / 2;
DNC(l, mid);
sufmx[mid] = 0;
for (int x = mid - 1; x >= l; x--)
{
sufmx[x] = max(sufmx[x + 1], c[x + 1]);
}
premx[mid] = 0;
for (int x = mid + 1; x <= r; x++)
{
premx[x] = max(premx[x - 1], c[x]);
}
Reset();
int y = mid;
for (int x = mid + 1; x <= r; x++)
{
while (y >= l && sufmx[y] <= premx[x])
{
Add(Line(y, F[y]));
y--;
}
F[x] = min(F[x], Query(-premx[x]) + 1ll * x * premx[x] + arr[x]);
}
Reset();
y = l;
for (int x = r; x > mid; x--)
{
while (y <= mid && sufmx[y] >= premx[x])
{
Add(Line(sufmx[y], F[y] - y * sufmx[y]));
y++;
}
F[x] = min(F[x], Query(x) + arr[x]);
}
DNC(mid + 1, r);
}
void Exc()
{
F[0] = 0;
for (int x = 1; x <= n; x++)
{
F[x] = inf;
}
DNC(0, n);
cout << F[n];
}
int main()
{
//freopen("D.INP", "r", stdin);
//freopen("D.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int x = 1; x <= test; x++)
{
Inp();
Exc();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11908kb
input:
4 3 1 4 1 5 9 2
output:
15
result:
ok "15"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11900kb
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: 11852kb
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: 1ms
memory: 11784kb
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: 11848kb
input:
5 191890310 576823355 782177068 404011431 818008580 839296263 462224593 492601449 384836991
output:
4069897043
result:
ok "4069897043"
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 11904kb
input:
6 138996221 501899080 353195922 545531545 910748511 350034067 160449218 155374934 840594328 164163676 797829355
output:
4158815683
result:
wrong answer 1st words differ - expected: '3921700772', found: '4158815683'