QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#506657#9127. Optimal Train Operationhos_lyricRE 0ms3856kbC++144.2kb2024-08-05 20:30:202024-08-05 20:30:21

Judging History

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

  • [2024-08-05 20:30:21]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3856kb
  • [2024-08-05 20:30:20]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


constexpr Int INF = 1001001001001001001LL;

/*
  min
  slope: decr.
  eval at: decr.
*/
struct Cht {
  vector<pair<Int, Int>> stack;
  Cht() {
// cerr<<"[Cht]"<<endl;
  }
  ~Cht() {
// cerr<<"[~Cht]"<<endl;
  }
  void add(Int p, Int q) {
// cerr<<"  [add] "<<p<<" "<<q<<endl;
    if (stack.size() >= 1) assert(stack.back().first >= p);
stack.emplace_back(p,q);return;
    if (stack.size() >= 1 && stack.back().first == p) {
      if (stack.back().second <= q) {
        return;
      } else {
        stack.pop_back();
      }
    }
    for (; stack.size() >= 2; ) {
      const Int p2 = stack.end()[-2].first, q2 = stack.end()[-2].second;
      const Int p1 = stack.end()[-1].first, q1 = stack.end()[-1].second;
      // (q1 - q2) / (p2 - p1) < (q - q1) / (p1 - p)
      if ((q1 - q2) * (p1 - p) < (q - q1) * (p2 - p1)) {
        break;
      } else {
        stack.pop_back();
      }
    }
    stack.emplace_back(p, q);
  }
  Int get(Int x) {
// cerr<<"  [get] "<<x<<endl;
Int mn=INF;for(const auto&l:stack)chmin(mn,l.first*x+l.second);return mn;
    for (; stack.size() >= 2; ) {
      const Int p2 = stack.end()[-2].first, q2 = stack.end()[-2].second;
      const Int p1 = stack.end()[-1].first, q1 = stack.end()[-1].second;
      if (p2 * x + q2 > p1 * x + q1) {
        break;
      } else {
        stack.pop_back();
      }
    }
    return stack.size() ? (stack.back().first * x + stack.back().second) : INF;
  }
};

int N;
vector<Int> C, A;

vector<Int> dp;

void rec(int l, int r) {
  if (l + 1 == r) {
    chmin(dp[r], dp[l] + A[l] + C[l]);
  } else {
    const int m = (l + r) / 2;
    rec(l, m);
    
    // [l, m) -> (m, r]
    // max in left
    {
      Int c = 0;
      vector<vector<pair<Int, Int>>> liness(r - m + 1);
      for (int i = m, j = m; --i >= l; ) {
        chmax(c, C[i]);
        for (; j < r && c >= C[j]; ++j) {}
        // dp[i] + A[i] + c (j - i)
        liness[j - m].emplace_back(c, dp[i] + A[i] - c * i);
      }
      Cht cht;
      for (int j = r; j > m; --j) {
        for (const auto &line : liness[j - m]) cht.add(line.first, line.second);
        const Int res = cht.get(j);
        chmin(dp[j], res);
      }
    }
    // max in right
    {
      Int c = 0;
      Cht cht;
      for (int i = m, j = m; ++j <= r; ) {
        chmax(c, C[j - 1]);
        for (; i > l && C[i - 1] <= c; ) {
          --i;
          // dp[i] + A[i] + c (j - i)
          cht.add(i, dp[i] + A[i]);
        }
        const Int res = cht.get(-c);
        chmin(dp[j], res + c * j);
      }
    }
    
    rec(m, r);
  }
}

int main() {
  for (; ~scanf("%d", &N); ) {
    C.resize(N);
    for (int i = 0; i < N; ++i) scanf("%lld", &C[i]);
    A.assign(N + 1, 0);
    for (int i = 1; i < N; ++i) scanf("%lld", &A[i]);
// reverse(C.begin(),C.end());
// reverse(A.begin(),A.end());
    
    dp.assign(N + 1, INF);
    dp[0] = 0;
    rec(0, N);
// cerr<<"dp = "<<dp<<endl;
    printf("%lld\n", dp[N]);
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3772kb

input:

4
3 1 4 1
5 9 2

output:

15

result:

ok "15"

Test #2:

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

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

input:

7
476190629 262703497 211047202 971407775 628894325 731963982 822804784
877914575 602436426 24979445 861648772 623690081 433933447

output:

5339182432

result:

ok "5339182432"

Test #4:

score: -100
Runtime Error

input:

8
910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016
430302156 982631932 161735902 880895728 923078537 707723857 189330739

output:


result: