QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#731660#9127. Optimal Train OperationcpismylifeOwOWA 2ms11908kbC++203.4kb2024-11-10 10:19:012024-11-10 10:19:01

Judging History

你现在查看的是最新测评结果

  • [2024-11-10 10:19:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11908kb
  • [2024-11-10 10:19:01]
  • 提交

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'