QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717211#9127. Optimal Train OperationduckindogWA 4ms23860kbC++232.4kb2024-11-06 17:15:062024-11-06 17:15:07

Judging History

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

  • [2024-11-06 17:15:07]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:23860kb
  • [2024-11-06 17:15:06]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 500'000 + 10;
int n;
int c[N], a[N];

struct Line { 
  long long a, b;
  Line() : a(0), b(0) {}
  Line(long long a, long long b) : a(a), b(b) {}
  double x(Line rhs) { return 1.0 * (b - rhs.b) / (rhs.a - a); }
};
struct CHT { 
  Line convex[N];
  int top;
  void clear() { top = 0; }
  void add(Line line) { 
    while (top > 1 && convex[top - 1].x(convex[top]) <= convex[top - 1].x(line)) 
      top -= 1;
    convex[++top] = line;
  }
} T;

int bwd[N], fwd[N];

long long f[N];
void dnc(int l, int r) { 
  if (l == r) return;
  int mid = (l + r) >> 1;
  dnc(l, mid);

  bwd[mid] = c[mid];
  for (int i = mid - 1; i >= l; --i) bwd[i] = max(bwd[i + 1], c[i]);

  fwd[mid + 1] = c[mid];
  for (int i = mid + 2; i <= r; ++i) fwd[i] = max(fwd[i - 1], c[i - 1]);

  { //max at right side
    T.clear();

    int it = mid;
    for (int i = mid + 1; i <= r; ++i) { 
      const int ma = fwd[i];
      while (it >= l && ma >= bwd[it]) { 
        T.add({-it, f[it]});
        it -= 1;
      }
      if (!T.top) continue;

      auto get = [&](int it) { 
        return 1ll * (T.convex[it].a + i) * ma + T.convex[it].b + a[i];
      };

      int l = 1, r = T.top - 1, pos = 1;
      while (l <= r) { 
        int mid = (l + r) >> 1;
        if (get(mid) >= get(mid + 1)) l = pos = mid + 1;
        else r = mid - 1;
      }

      f[i] = min(f[i], get(pos));
    }
  } 

  { //max at left side
    T.clear();

    int it = l;
    for (int i = r; i >= mid + 1; --i) { 
      while (it <= mid && bwd[it] >= fwd[i]) { 
        T.add({bwd[it], f[it] - 1ll * bwd[it] * it});
        it += 1;
      }
      if (!T.top) continue;

      auto get = [&](int it) { 
        return 1ll * T.convex[it].a * i + T.convex[it].b + a[i];
      };

      int l = 1, r = T.top - 1, pos = 1;
      while (l <= r) { 
        int mid = (l + r) >> 1;
        if (get(mid) >= get(mid + 1)) l = pos = mid + 1;
        else r = mid - 1;
      }

      f[i] = min(f[i], get(pos));
    }
  }

  dnc(mid + 1, r);
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 0; i < n; ++i) cin >> c[i];
  for (int i = 1; i < n; ++i) cin >> a[i];

  memset(f, 14, sizeof f);
  f[0] = 0;
  dnc(0, n + 1);

  cout << f[n + 1] << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
3 1 4 1
5 9 2

output:

15

result:

ok "15"

Test #2:

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

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: 3ms
memory: 22436kb

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: 4ms
memory: 21264kb

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

input:

5
191890310 576823355 782177068 404011431 818008580
839296263 462224593 492601449 384836991

output:

4069897043

result:

ok "4069897043"

Test #6:

score: 0
Accepted
time: 2ms
memory: 22296kb

input:

6
138996221 501899080 353195922 545531545 910748511 350034067
160449218 155374934 840594328 164163676 797829355

output:

3921700772

result:

ok "3921700772"

Test #7:

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

input:

2
824284691 533206504
470338674

output:

1648569382

result:

ok "1648569382"

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 21108kb

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:

902769

result:

wrong answer 1st words differ - expected: '892773', found: '902769'