oj.uz

Submission #282450

# Submission time Handle Problem Language Result Execution time Memory
282450 2020-08-24T12:32:02 Z rama_pang Long Distance Coach (JOI17_coach) C++14
71 / 100
 2000 ms 14684 KB 
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const lint INF = 2e18;
const int MAXN = 2e5 + 5;

template<typename A, typename B>
void chmin(A &a, const B &b) { a = min(a, b); }

template<typename A, typename B>
void chmax(A &a, const B &b) { a = max(a, b); }

struct Line {
  lint a, b;
  Line() : a(0), b(INF) {}
  Line(lint a, lint b) : a(a), b(b) {}
  lint get(lint x) {
    return a * x + b;
  }
};

class LiChao {
 private:
  struct Node {
    Line line = Line();
    Node *lc = nullptr;
    Node *rc = nullptr;
  };

  lint sz;
  Node *root = nullptr;

  void InsertLineKnowingly(Node* &n, lint tl, lint tr, Line x) {
    if (n == nullptr) n = new Node();
    if (n->line.get(tl) > x.get(tl)) swap(n->line, x);
    if (n->line.get(tr) <= x.get(tr)) return;
    if (tl == tr) return;
    lint mid = (tl + tr) / 2;
    if (n->line.get(mid) < x.get(mid)) {
      InsertLineKnowingly(n->rc, mid + 1, tr, x);
    } else {
      swap(n->line, x);
      InsertLineKnowingly(n->lc, tl, mid, x);
    }
  }

  void InsertLine(Node* &n, lint tl, lint tr, lint l, lint r, Line x) {
    if (tr < l || r < tl || tl > tr || l > r) return;
    if (n == nullptr) n = new Node();
    if (l <= tl && tr <= r) return InsertLineKnowingly(n, tl, tr, x);
    lint mid = (tl + tr) / 2;
    InsertLine(n->lc, tl, mid, l, r, x);
    InsertLine(n->rc, mid + 1, tr, l, r, x);
  }

  lint Query(Node* &n, lint tl, lint tr, lint x) {
    if (n == nullptr) return INF;
    if (tl == tr) return n->line.get(x);
    lint res = n->line.get(x);
    lint mid = (tl + tr) / 2;
    if (x <= mid) {
      res = min(res, Query(n->lc, tl, mid, x));
    } else {
      res = min(res, Query(n->rc, mid + 1, tr, x));
    }
    return res;
  }

 public:
  LiChao() {}
  LiChao(lint sz) : sz(sz) {}
  vector<Line> all;
  void InsertLine(lint l, lint r, Line x) {
    return InsertLine(root, 0, sz - 1, l, r, x);
  }
  lint Query(lint x) {
    return min(INF, Query(root, 0, sz - 1, x));
  }
};

int N, M;
lint X, W, T;
LiChao li_chao(INF);
lint S[MAXN], P[MAXN];
pair<lint, lint> A[MAXN];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> X >> N >> M >> W >> T;
  for (int i = 0; i < N; i++) {
    cin >> S[i];
  }
  S[N] = X;
  vector<int> order(N + 1);
  iota(begin(order), end(order), 0);
  sort(begin(order), end(order), [&](int i, int j) {
    return (S[i] % T) < (S[j] % T);
  });

  for (int i = 0; i < M; i++) {
    cin >> A[i].first >> A[i].second;
  }
  sort(A, A + M);
  for (int i = 0; i < M; i++) {
    P[i + 1] = P[i] + A[i].second;
  }
  
  // vector<vector<pair<int, lint>>> adj(M + 1);
  // for (int i = 0; i <= N; i++) {
  //   int p = upper_bound(A, A + M, make_pair(S[i] % T, -1ll)) - A;
  //   lint total_weight = 0;
  //   for (int j = p - 1; j >= 0; j--) {
  //     lint weight = A[j].second + S[i] / T * W;
  //     total_weight += weight;
  //     adj[j].emplace_back(p, total_weight);
  //   }
  // }

  // At time t1 delete [a, b].
  // At time t2 delete [c, d].
  // Then [a, b] and [c, d] will never overlap in optimal answer.
  // If they overlap, we can delete the overlapping region at min(t1, t2) to get more benefit.
  // This is possible since we can keep extending both a and b to the left until 0.

  vector<lint> dp(M + 1, INF);
  dp[0] = (X + T - 1) / T * W;
  for (int i = 0, ptr = 0; i < M; i++) {
    chmin(dp[i + 1], dp[i] + (X + T - 1 - A[i].first) / T * W);
    li_chao.InsertLine(0, INF - 1, Line(-i, dp[i] - P[i]));
    while (ptr <= N) {
      int p = upper_bound(A, A + M, make_pair(S[order[ptr]] % T, -1ll)) - A;
      if (p < i + 1) {
        ptr += 1;
        continue;
      }
      if (p == i + 1) {
        // lint x = S[order[ptr]] / T * W;
        // chmin(dp[i + 1], (i + 1) * x + P[i + 1] + li_chao.Query(x));
        lint total_weight = 0;
        for (int j = i; j >= 0; j--) {
          lint weight = A[j].second + S[order[ptr]] / T * W;
          total_weight += weight;
          chmin(dp[i + 1], dp[j] + total_weight);
        }
        ptr += 1;
      } else {
        break;
      }
    }
  }

  cout << dp[M] << "\n";
  return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 416 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 416 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 0 ms 384 KB Output is correct
28 Correct 0 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 416 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 0 ms 384 KB Output is correct
28 Correct 0 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 5 ms 512 KB Output is correct
39 Correct 6 ms 512 KB Output is correct
40 Correct 5 ms 512 KB Output is correct
41 Correct 7 ms 512 KB Output is correct
42 Correct 5 ms 512 KB Output is correct
43 Correct 6 ms 512 KB Output is correct
44 Correct 5 ms 512 KB Output is correct
45 Correct 5 ms 512 KB Output is correct
46 Correct 4 ms 512 KB Output is correct
47 Correct 5 ms 544 KB Output is correct
48 Correct 5 ms 532 KB Output is correct
49 Correct 5 ms 512 KB Output is correct
50 Correct 5 ms 512 KB Output is correct
51 Correct 5 ms 512 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 416 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 0 ms 384 KB Output is correct
28 Correct 0 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 5 ms 512 KB Output is correct
39 Correct 6 ms 512 KB Output is correct
40 Correct 5 ms 512 KB Output is correct
41 Correct 7 ms 512 KB Output is correct
42 Correct 5 ms 512 KB Output is correct
43 Correct 6 ms 512 KB Output is correct
44 Correct 5 ms 512 KB Output is correct
45 Correct 5 ms 512 KB Output is correct
46 Correct 4 ms 512 KB Output is correct
47 Correct 5 ms 544 KB Output is correct
48 Correct 5 ms 532 KB Output is correct
49 Correct 5 ms 512 KB Output is correct
50 Correct 5 ms 512 KB Output is correct
51 Correct 5 ms 512 KB Output is correct
52 Execution timed out 2068 ms 14684 KB Time limit exceeded
53 Halted 0 ms 0 KB -