QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#763661#9127. Optimal Train OperationghijkWA 2ms11932kbC++203.7kb2024-11-19 21:32:142024-11-19 21:32:15

Judging History

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

  • [2024-11-19 21:32:15]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11932kb
  • [2024-11-19 21:32:14]
  • 提交

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 Line {
    long long a, b;
    Line(long long a = 0, long long b = oo): a(a), b(b) {}
    long long eval(long long x) { return a * x + b; }
};
vector <Line> lines; int ptr;
bool bad(Line a, Line b, Line c) { return (long double) (c.b - a.b) / (a.a - c.a) < (long double) (b.b - a.b) / (a.a - b.a); }
void add(long long a, long long b) {
    Line l(a, b);
    while (lines.size() >= 2 && bad(lines.end()[-2], lines.back(), l)) lines.pop_back();
    lines.push_back(l);
}
ll get(long long x) {
    if (ptr >= (int) lines.size()) ptr = (int) lines.size() - 1;
    while (ptr < (int) lines.size() - 1 && lines[ptr].eval(x) > lines[ptr + 1].eval(x)) ++ptr;
    return lines[ptr].a * x + lines[ptr].b ;
}

void clear(){
    lines.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();
    for (int i = mid + 1, j = mid; i <= r; ++i){
        while (j >= l && suf[j] <= pre[i]) {
             add(j, dp[j]);
            --j;
        }
        minimize(dp[i], get(-pre[i]) + 1ll * i * pre[i] + a[i]);
    }

    clear();
    for (int i = r, j = l; i > mid; --i){
        while (j <= mid && suf[j] >= pre[i]){
            add(suf[j], (dp[j] - 1ll * j * suf[j]));
            ++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 + 5, 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: 0
Wrong Answer
time: 2ms
memory: 11932kb

input:

4
3 1 4 1
5 9 2

output:

-140304673890093

result:

wrong answer 1st words differ - expected: '15', found: '-140304673890093'