QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#763606#9127. Optimal Train OperationghijkWA 2ms11920kbC++203.9kb2024-11-19 21:10:352024-11-19 21:10:43

Judging History

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

  • [2024-11-19 21:10:43]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11920kb
  • [2024-11-19 21:10:35]
  • 提交

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 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: 2ms
memory: 11920kb

input:

4
3 1 4 1
5 9 2

output:

15

result:

ok "15"

Test #2:

score: 0
Accepted
time: 0ms
memory: 11848kb

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: 1ms
memory: 11848kb

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: 11904kb

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: 0
Accepted
time: 1ms
memory: 11780kb

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: 11848kb

input:

2
824284691 533206504
470338674

output:

1648569382

result:

ok "1648569382"

Test #8:

score: -100
Wrong Answer
time: 2ms
memory: 11912kb

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'