oj.uz

Submission #857890

# Submission time Handle Problem Language Result Execution time Memory
857890 2023-10-07T06:57:48 Z rxlfd314 Two Dishes (JOI19_dishes) C++17
100 / 100
 4691 ms 218768 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using arl2 = array<ll, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)

constexpr int mxN = 1000001;
constexpr ll NINF = 0xc0c0c0c0c0c0c0c0;
int N, M;
ll A[mxN], B[mxN], P[mxN], Q[mxN], S[mxN], T[mxN];

ll dp[1001][1001];
void naive_dp() {
  memset(dp, 0xc0, sizeof(dp));
  dp[0][0] = 0;
  FOR(i, 0, N)
    FOR(j, 0, M) {
      if (i || j)
        dp[i][j] = max(i ? dp[i-1][j] + P[i] * (A[i] - S[i] <= -B[j]) : NINF, j ? dp[i][j-1] + Q[j] * (A[i] <= T[j] - B[j]) : NINF);
      cout << dp[i][j] << "\n "[j<M];
    }
  cout << '\n';
}

#define lc i << 1
#define rc i << 1 | 1
ll fp[mxN<<2], p[mxN<<2], lz_max[mxN<<2], lz_add[mxN<<2];
void push(int i) {
  auto apply = [&](int j) {
    fp[j] += lz_add[i];
    lz_add[j] += lz_add[i];
    lz_max[j] += lz_add[i];
    chmax(lz_max[j], lz_max[i]);
    chmax(fp[j], lz_max[i]);
    p[j] += p[i];
  };
  apply(lc);
  apply(rc);
  lz_max[i] = NINF;
  lz_add[i] = p[i] = 0;
}
void upd(int ql, int qr, ll v, int key, int i = 1, int tl = 0, int tr = M) {
  if (tl > qr || tr < ql)
    return;
  if (ql <= tl && tr <= qr) {
    if (!key)
      p[i] += v;
    else if (key < 2)
      lz_add[i] += v, lz_max[i] += v, fp[i] += v;
    else
      chmax(lz_max[i], v), chmax(fp[i], v);
    return;
  }
  push(i);
  int tm = tl + tr >> 1;
  upd(ql, qr, v, key, lc, tl, tm);
  upd(ql, qr, v, key, rc, tm+1, tr);
  fp[i] = max(fp[lc], fp[rc]);
}
ll qry(int ql, int qr, bool key = 0, int i = 1, int tl = 0, int tr = M) {
  if (tl > qr || tr < ql)
    return NINF;
  if (ql <= tl && tr <= qr)
    return key ? fp[i] + p[i] : fp[i];
  push(i);
  int tm = tl + tr >> 1;
  return max(qry(ql, qr, key, lc, tl, tm), qry(ql, qr, key, rc, tm+1, tr));
}
void print(int i = 1, int tl = 0, int tr = M) {
  if (tl == tr)
    cout << fp[i] + p[i] << "\n "[tl<M];
  else {
    push(i);
    int tm = tl + tr >> 1;
    print(lc, tl, tm);
    print(rc, tm+1, tr);
  }
}
#undef lc
#undef rc

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  // range update
  // 0: update transitions
  // 1: add P[i]
  // 2: range max update
  cin >> N >> M;
  FOR(i, 1, N)
    cin >> A[i] >> S[i] >> P[i], A[i] += A[i-1];
  memset(lz_max, 0xc0, sizeof(lz_max));
  priority_queue<arl2, vt<arl2>, greater<arl2>> pq;
  FOR(i, 1, M) {
    cin >> B[i] >> T[i] >> Q[i], B[i] += B[i-1];
    if (T[i] - B[i] >= 0) {
      pq.push({T[i] - B[i], i});
      upd(i, M, Q[i], 0);
    }
  }
#ifdef DEBUG
  naive_dp();
  print();
#endif
  
  FOR(i, 1, N) {
    int ind = upper_bound(B, B+M+1, S[i]-A[i]) - B - 1;
    vt<int> vec;
    while (size(pq) && pq.top()[0] < A[i]) {
      int j = pq.top()[1];
      vec.push_back(j);
      upd(j, M, -Q[j], 0);
      upd(j, M, Q[j], 1);
      pq.pop();
    }
    if (~ind) {
      vec.push_back(ind);
      upd(0, ind, P[i], 1);
    }
    sort(all(vec));
    for (int j : vec)
      upd(j, M, qry(0, j), 2);
#ifdef DEBUG
    print();
#endif
  }

  cout << qry(M, M, 1) << '\n';
}

Compilation message

dishes.cpp: In function 'void upd(int, int, ll, int, int, int, int)':
dishes.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
dishes.cpp: In function 'll qry(int, int, bool, int, int, int)':
dishes.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
dishes.cpp: In function 'void print(int, int, int)':
dishes.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int tm = tl + tr >> 1;
      |              ~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 68804 KB Output is correct
2 Correct 472 ms 69828 KB Output is correct
3 Correct 215 ms 69504 KB Output is correct
4 Correct 348 ms 66628 KB Output is correct
5 Correct 5 ms 45404 KB Output is correct
6 Correct 415 ms 69184 KB Output is correct
7 Correct 104 ms 65776 KB Output is correct
8 Correct 66 ms 49620 KB Output is correct
9 Correct 218 ms 69432 KB Output is correct
10 Correct 487 ms 69828 KB Output is correct
11 Correct 189 ms 69420 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 6 ms 45404 KB Output is correct
3 Correct 5 ms 45404 KB Output is correct
4 Correct 5 ms 45400 KB Output is correct
5 Correct 6 ms 45404 KB Output is correct
6 Correct 6 ms 45580 KB Output is correct
7 Correct 6 ms 45404 KB Output is correct
8 Correct 5 ms 45588 KB Output is correct
9 Correct 6 ms 45404 KB Output is correct
10 Correct 5 ms 45572 KB Output is correct
11 Correct 5 ms 45400 KB Output is correct
12 Correct 5 ms 45404 KB Output is correct
13 Correct 6 ms 45516 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45576 KB Output is correct
16 Correct 5 ms 45520 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 6 ms 45404 KB Output is correct
3 Correct 5 ms 45404 KB Output is correct
4 Correct 5 ms 45400 KB Output is correct
5 Correct 6 ms 45404 KB Output is correct
6 Correct 6 ms 45580 KB Output is correct
7 Correct 6 ms 45404 KB Output is correct
8 Correct 5 ms 45588 KB Output is correct
9 Correct 6 ms 45404 KB Output is correct
10 Correct 5 ms 45572 KB Output is correct
11 Correct 5 ms 45400 KB Output is correct
12 Correct 5 ms 45404 KB Output is correct
13 Correct 6 ms 45516 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45576 KB Output is correct
16 Correct 5 ms 45520 KB Output is correct
17 Correct 7 ms 45660 KB Output is correct
18 Correct 8 ms 45784 KB Output is correct
19 Correct 9 ms 45660 KB Output is correct
20 Correct 8 ms 45656 KB Output is correct
21 Correct 9 ms 45956 KB Output is correct
22 Correct 9 ms 45660 KB Output is correct
23 Correct 9 ms 45660 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 6 ms 45404 KB Output is correct
3 Correct 5 ms 45404 KB Output is correct
4 Correct 5 ms 45400 KB Output is correct
5 Correct 6 ms 45404 KB Output is correct
6 Correct 6 ms 45580 KB Output is correct
7 Correct 6 ms 45404 KB Output is correct
8 Correct 5 ms 45588 KB Output is correct
9 Correct 6 ms 45404 KB Output is correct
10 Correct 5 ms 45572 KB Output is correct
11 Correct 5 ms 45400 KB Output is correct
12 Correct 5 ms 45404 KB Output is correct
13 Correct 6 ms 45516 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45576 KB Output is correct
16 Correct 5 ms 45520 KB Output is correct
17 Correct 7 ms 45660 KB Output is correct
18 Correct 8 ms 45784 KB Output is correct
19 Correct 9 ms 45660 KB Output is correct
20 Correct 8 ms 45656 KB Output is correct
21 Correct 9 ms 45956 KB Output is correct
22 Correct 9 ms 45660 KB Output is correct
23 Correct 9 ms 45660 KB Output is correct
24 Correct 215 ms 73572 KB Output is correct
25 Correct 502 ms 77160 KB Output is correct
26 Correct 283 ms 73444 KB Output is correct
27 Correct 383 ms 75360 KB Output is correct
28 Correct 345 ms 75716 KB Output is correct
29 Correct 219 ms 75388 KB Output is correct
30 Correct 739 ms 74956 KB Output is correct
31 Correct 253 ms 68928 KB Output is correct
32 Correct 56 ms 52348 KB Output is correct
33 Correct 412 ms 73160 KB Output is correct
34 Correct 600 ms 75712 KB Output is correct
35 Correct 668 ms 71656 KB Output is correct
36 Correct 652 ms 71756 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 6 ms 45404 KB Output is correct
3 Correct 5 ms 45404 KB Output is correct
4 Correct 5 ms 45400 KB Output is correct
5 Correct 6 ms 45404 KB Output is correct
6 Correct 6 ms 45580 KB Output is correct
7 Correct 6 ms 45404 KB Output is correct
8 Correct 5 ms 45588 KB Output is correct
9 Correct 6 ms 45404 KB Output is correct
10 Correct 5 ms 45572 KB Output is correct
11 Correct 5 ms 45400 KB Output is correct
12 Correct 5 ms 45404 KB Output is correct
13 Correct 6 ms 45516 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45576 KB Output is correct
16 Correct 5 ms 45520 KB Output is correct
17 Correct 7 ms 45660 KB Output is correct
18 Correct 8 ms 45784 KB Output is correct
19 Correct 9 ms 45660 KB Output is correct
20 Correct 8 ms 45656 KB Output is correct
21 Correct 9 ms 45956 KB Output is correct
22 Correct 9 ms 45660 KB Output is correct
23 Correct 9 ms 45660 KB Output is correct
24 Correct 215 ms 73572 KB Output is correct
25 Correct 502 ms 77160 KB Output is correct
26 Correct 283 ms 73444 KB Output is correct
27 Correct 383 ms 75360 KB Output is correct
28 Correct 345 ms 75716 KB Output is correct
29 Correct 219 ms 75388 KB Output is correct
30 Correct 739 ms 74956 KB Output is correct
31 Correct 253 ms 68928 KB Output is correct
32 Correct 56 ms 52348 KB Output is correct
33 Correct 412 ms 73160 KB Output is correct
34 Correct 600 ms 75712 KB Output is correct
35 Correct 668 ms 71656 KB Output is correct
36 Correct 652 ms 71756 KB Output is correct
37 Correct 282 ms 74944 KB Output is correct
38 Correct 465 ms 77340 KB Output is correct
39 Correct 528 ms 75136 KB Output is correct
40 Correct 529 ms 75508 KB Output is correct
41 Correct 6 ms 45404 KB Output is correct
42 Correct 778 ms 76448 KB Output is correct
43 Correct 429 ms 74860 KB Output is correct
44 Correct 611 ms 76248 KB Output is correct
45 Correct 685 ms 73268 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 6 ms 45404 KB Output is correct
3 Correct 5 ms 45404 KB Output is correct
4 Correct 5 ms 45400 KB Output is correct
5 Correct 6 ms 45404 KB Output is correct
6 Correct 6 ms 45580 KB Output is correct
7 Correct 6 ms 45404 KB Output is correct
8 Correct 5 ms 45588 KB Output is correct
9 Correct 6 ms 45404 KB Output is correct
10 Correct 5 ms 45572 KB Output is correct
11 Correct 5 ms 45400 KB Output is correct
12 Correct 5 ms 45404 KB Output is correct
13 Correct 6 ms 45516 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45576 KB Output is correct
16 Correct 5 ms 45520 KB Output is correct
17 Correct 7 ms 45660 KB Output is correct
18 Correct 8 ms 45784 KB Output is correct
19 Correct 9 ms 45660 KB Output is correct
20 Correct 8 ms 45656 KB Output is correct
21 Correct 9 ms 45956 KB Output is correct
22 Correct 9 ms 45660 KB Output is correct
23 Correct 9 ms 45660 KB Output is correct
24 Correct 215 ms 73572 KB Output is correct
25 Correct 502 ms 77160 KB Output is correct
26 Correct 283 ms 73444 KB Output is correct
27 Correct 383 ms 75360 KB Output is correct
28 Correct 345 ms 75716 KB Output is correct
29 Correct 219 ms 75388 KB Output is correct
30 Correct 739 ms 74956 KB Output is correct
31 Correct 253 ms 68928 KB Output is correct
32 Correct 56 ms 52348 KB Output is correct
33 Correct 412 ms 73160 KB Output is correct
34 Correct 600 ms 75712 KB Output is correct
35 Correct 668 ms 71656 KB Output is correct
36 Correct 652 ms 71756 KB Output is correct
37 Correct 282 ms 74944 KB Output is correct
38 Correct 465 ms 77340 KB Output is correct
39 Correct 528 ms 75136 KB Output is correct
40 Correct 529 ms 75508 KB Output is correct
41 Correct 6 ms 45404 KB Output is correct
42 Correct 778 ms 76448 KB Output is correct
43 Correct 429 ms 74860 KB Output is correct
44 Correct 611 ms 76248 KB Output is correct
45 Correct 685 ms 73268 KB Output is correct
46 Correct 1569 ms 174100 KB Output is correct
47 Correct 2150 ms 182424 KB Output is correct
48 Correct 2743 ms 175504 KB Output is correct
49 Correct 2669 ms 175236 KB Output is correct
50 Correct 4580 ms 181956 KB Output is correct
51 Correct 2516 ms 172724 KB Output is correct
52 Correct 3734 ms 180364 KB Output is correct
53 Correct 4329 ms 166852 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 68804 KB Output is correct
2 Correct 472 ms 69828 KB Output is correct
3 Correct 215 ms 69504 KB Output is correct
4 Correct 348 ms 66628 KB Output is correct
5 Correct 5 ms 45404 KB Output is correct
6 Correct 415 ms 69184 KB Output is correct
7 Correct 104 ms 65776 KB Output is correct
8 Correct 66 ms 49620 KB Output is correct
9 Correct 218 ms 69432 KB Output is correct
10 Correct 487 ms 69828 KB Output is correct
11 Correct 189 ms 69420 KB Output is correct
12 Correct 5 ms 45400 KB Output is correct
13 Correct 6 ms 45404 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45400 KB Output is correct
16 Correct 6 ms 45404 KB Output is correct
17 Correct 6 ms 45580 KB Output is correct
18 Correct 6 ms 45404 KB Output is correct
19 Correct 5 ms 45588 KB Output is correct
20 Correct 6 ms 45404 KB Output is correct
21 Correct 5 ms 45572 KB Output is correct
22 Correct 5 ms 45400 KB Output is correct
23 Correct 5 ms 45404 KB Output is correct
24 Correct 6 ms 45516 KB Output is correct
25 Correct 5 ms 45404 KB Output is correct
26 Correct 5 ms 45576 KB Output is correct
27 Correct 5 ms 45520 KB Output is correct
28 Correct 7 ms 45660 KB Output is correct
29 Correct 8 ms 45784 KB Output is correct
30 Correct 9 ms 45660 KB Output is correct
31 Correct 8 ms 45656 KB Output is correct
32 Correct 9 ms 45956 KB Output is correct
33 Correct 9 ms 45660 KB Output is correct
34 Correct 9 ms 45660 KB Output is correct
35 Correct 215 ms 73572 KB Output is correct
36 Correct 502 ms 77160 KB Output is correct
37 Correct 283 ms 73444 KB Output is correct
38 Correct 383 ms 75360 KB Output is correct
39 Correct 345 ms 75716 KB Output is correct
40 Correct 219 ms 75388 KB Output is correct
41 Correct 739 ms 74956 KB Output is correct
42 Correct 253 ms 68928 KB Output is correct
43 Correct 56 ms 52348 KB Output is correct
44 Correct 412 ms 73160 KB Output is correct
45 Correct 600 ms 75712 KB Output is correct
46 Correct 668 ms 71656 KB Output is correct
47 Correct 652 ms 71756 KB Output is correct
48 Correct 282 ms 74944 KB Output is correct
49 Correct 465 ms 77340 KB Output is correct
50 Correct 528 ms 75136 KB Output is correct
51 Correct 529 ms 75508 KB Output is correct
52 Correct 6 ms 45404 KB Output is correct
53 Correct 778 ms 76448 KB Output is correct
54 Correct 429 ms 74860 KB Output is correct
55 Correct 611 ms 76248 KB Output is correct
56 Correct 685 ms 73268 KB Output is correct
57 Correct 280 ms 75208 KB Output is correct
58 Correct 427 ms 76964 KB Output is correct
59 Correct 495 ms 81344 KB Output is correct
60 Correct 538 ms 81600 KB Output is correct
61 Correct 682 ms 80304 KB Output is correct
62 Correct 5 ms 45400 KB Output is correct
63 Correct 724 ms 84068 KB Output is correct
64 Correct 394 ms 81212 KB Output is correct
65 Correct 619 ms 83420 KB Output is correct
66 Correct 708 ms 76988 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 68804 KB Output is correct
2 Correct 472 ms 69828 KB Output is correct
3 Correct 215 ms 69504 KB Output is correct
4 Correct 348 ms 66628 KB Output is correct
5 Correct 5 ms 45404 KB Output is correct
6 Correct 415 ms 69184 KB Output is correct
7 Correct 104 ms 65776 KB Output is correct
8 Correct 66 ms 49620 KB Output is correct
9 Correct 218 ms 69432 KB Output is correct
10 Correct 487 ms 69828 KB Output is correct
11 Correct 189 ms 69420 KB Output is correct
12 Correct 5 ms 45400 KB Output is correct
13 Correct 6 ms 45404 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45400 KB Output is correct
16 Correct 6 ms 45404 KB Output is correct
17 Correct 6 ms 45580 KB Output is correct
18 Correct 6 ms 45404 KB Output is correct
19 Correct 5 ms 45588 KB Output is correct
20 Correct 6 ms 45404 KB Output is correct
21 Correct 5 ms 45572 KB Output is correct
22 Correct 5 ms 45400 KB Output is correct
23 Correct 5 ms 45404 KB Output is correct
24 Correct 6 ms 45516 KB Output is correct
25 Correct 5 ms 45404 KB Output is correct
26 Correct 5 ms 45576 KB Output is correct
27 Correct 5 ms 45520 KB Output is correct
28 Correct 7 ms 45660 KB Output is correct
29 Correct 8 ms 45784 KB Output is correct
30 Correct 9 ms 45660 KB Output is correct
31 Correct 8 ms 45656 KB Output is correct
32 Correct 9 ms 45956 KB Output is correct
33 Correct 9 ms 45660 KB Output is correct
34 Correct 9 ms 45660 KB Output is correct
35 Correct 215 ms 73572 KB Output is correct
36 Correct 502 ms 77160 KB Output is correct
37 Correct 283 ms 73444 KB Output is correct
38 Correct 383 ms 75360 KB Output is correct
39 Correct 345 ms 75716 KB Output is correct
40 Correct 219 ms 75388 KB Output is correct
41 Correct 739 ms 74956 KB Output is correct
42 Correct 253 ms 68928 KB Output is correct
43 Correct 56 ms 52348 KB Output is correct
44 Correct 412 ms 73160 KB Output is correct
45 Correct 600 ms 75712 KB Output is correct
46 Correct 668 ms 71656 KB Output is correct
47 Correct 652 ms 71756 KB Output is correct
48 Correct 282 ms 74944 KB Output is correct
49 Correct 465 ms 77340 KB Output is correct
50 Correct 528 ms 75136 KB Output is correct
51 Correct 529 ms 75508 KB Output is correct
52 Correct 6 ms 45404 KB Output is correct
53 Correct 778 ms 76448 KB Output is correct
54 Correct 429 ms 74860 KB Output is correct
55 Correct 611 ms 76248 KB Output is correct
56 Correct 685 ms 73268 KB Output is correct
57 Correct 1569 ms 174100 KB Output is correct
58 Correct 2150 ms 182424 KB Output is correct
59 Correct 2743 ms 175504 KB Output is correct
60 Correct 2669 ms 175236 KB Output is correct
61 Correct 4580 ms 181956 KB Output is correct
62 Correct 2516 ms 172724 KB Output is correct
63 Correct 3734 ms 180364 KB Output is correct
64 Correct 4329 ms 166852 KB Output is correct
65 Correct 280 ms 75208 KB Output is correct
66 Correct 427 ms 76964 KB Output is correct
67 Correct 495 ms 81344 KB Output is correct
68 Correct 538 ms 81600 KB Output is correct
69 Correct 682 ms 80304 KB Output is correct
70 Correct 5 ms 45400 KB Output is correct
71 Correct 724 ms 84068 KB Output is correct
72 Correct 394 ms 81212 KB Output is correct
73 Correct 619 ms 83420 KB Output is correct
74 Correct 708 ms 76988 KB Output is correct
75 Correct 1544 ms 210932 KB Output is correct
76 Correct 2291 ms 218768 KB Output is correct
77 Correct 2680 ms 205904 KB Output is correct
78 Correct 2730 ms 206040 KB Output is correct
79 Correct 4669 ms 217408 KB Output is correct
80 Correct 2503 ms 206260 KB Output is correct
81 Correct 3701 ms 213244 KB Output is correct
82 Correct 4691 ms 185072 KB Output is correct
83 Correct 4400 ms 205416 KB Output is correct