oj.uz

Submission #857835

# Submission time Handle Problem Language Result Execution time Memory
857835 2023-10-07T04:37:04 Z rxlfd314 Two Dishes (JOI19_dishes) C++17
74 / 100
 4003 ms 216900 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);
}
ll qry(int x, bool key = 0, int i = 1, int tl = 0, int tr = M) {
  if (tl == tr)
    return key ? fp[i] + p[i] : fp[i];
  push(i);
  int tm = tl + tr >> 1;
  return x > tm ? qry(x, key, rc, tm+1, tr) : qry(x, key, lc, tl, tm);
}
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(j), 2);
#ifdef DEBUG
    print();
#endif
  }

  cout << qry(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, bool, int, int, int)':
dishes.cpp:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
dishes.cpp: In function 'void print(int, int, int)':
dishes.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int tm = tl + tr >> 1;
      |              ~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 82356 KB Output is correct
2 Correct 406 ms 83236 KB Output is correct
3 Correct 228 ms 82744 KB Output is correct
4 Correct 306 ms 80480 KB Output is correct
5 Correct 6 ms 45400 KB Output is correct
6 Correct 369 ms 83756 KB Output is correct
7 Correct 97 ms 71620 KB Output is correct
8 Correct 68 ms 56656 KB Output is correct
9 Correct 229 ms 83856 KB Output is correct
10 Correct 417 ms 76908 KB Output is correct
11 Correct 204 ms 77632 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45404 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 45404 KB Output is correct
5 Correct 5 ms 45400 KB Output is correct
6 Correct 5 ms 45404 KB Output is correct
7 Correct 5 ms 45684 KB Output is correct
8 Correct 6 ms 45404 KB Output is correct
9 Correct 5 ms 45400 KB Output is correct
10 Correct 6 ms 45404 KB Output is correct
11 Correct 5 ms 45520 KB Output is correct
12 Correct 5 ms 45400 KB Output is correct
13 Correct 5 ms 45404 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45580 KB Output is correct
16 Correct 5 ms 45536 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45404 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 45404 KB Output is correct
5 Correct 5 ms 45400 KB Output is correct
6 Correct 5 ms 45404 KB Output is correct
7 Correct 5 ms 45684 KB Output is correct
8 Correct 6 ms 45404 KB Output is correct
9 Correct 5 ms 45400 KB Output is correct
10 Correct 6 ms 45404 KB Output is correct
11 Correct 5 ms 45520 KB Output is correct
12 Correct 5 ms 45400 KB Output is correct
13 Correct 5 ms 45404 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45580 KB Output is correct
16 Correct 5 ms 45536 KB Output is correct
17 Correct 7 ms 45660 KB Output is correct
18 Correct 8 ms 45816 KB Output is correct
19 Correct 9 ms 45660 KB Output is correct
20 Correct 7 ms 45660 KB Output is correct
21 Correct 8 ms 45844 KB Output is correct
22 Correct 8 ms 45660 KB Output is correct
23 Correct 8 ms 45600 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45404 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 45404 KB Output is correct
5 Correct 5 ms 45400 KB Output is correct
6 Correct 5 ms 45404 KB Output is correct
7 Correct 5 ms 45684 KB Output is correct
8 Correct 6 ms 45404 KB Output is correct
9 Correct 5 ms 45400 KB Output is correct
10 Correct 6 ms 45404 KB Output is correct
11 Correct 5 ms 45520 KB Output is correct
12 Correct 5 ms 45400 KB Output is correct
13 Correct 5 ms 45404 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45580 KB Output is correct
16 Correct 5 ms 45536 KB Output is correct
17 Correct 7 ms 45660 KB Output is correct
18 Correct 8 ms 45816 KB Output is correct
19 Correct 9 ms 45660 KB Output is correct
20 Correct 7 ms 45660 KB Output is correct
21 Correct 8 ms 45844 KB Output is correct
22 Correct 8 ms 45660 KB Output is correct
23 Correct 8 ms 45600 KB Output is correct
24 Correct 193 ms 78448 KB Output is correct
25 Correct 415 ms 82376 KB Output is correct
26 Correct 240 ms 78536 KB Output is correct
27 Correct 361 ms 80124 KB Output is correct
28 Correct 304 ms 79932 KB Output is correct
29 Correct 217 ms 81232 KB Output is correct
30 Correct 586 ms 80312 KB Output is correct
31 Correct 213 ms 71476 KB Output is correct
32 Correct 56 ms 54864 KB Output is correct
33 Correct 353 ms 78416 KB Output is correct
34 Correct 511 ms 80984 KB Output is correct
35 Correct 571 ms 73628 KB Output is correct
36 Correct 564 ms 73668 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45404 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 45404 KB Output is correct
5 Correct 5 ms 45400 KB Output is correct
6 Correct 5 ms 45404 KB Output is correct
7 Correct 5 ms 45684 KB Output is correct
8 Correct 6 ms 45404 KB Output is correct
9 Correct 5 ms 45400 KB Output is correct
10 Correct 6 ms 45404 KB Output is correct
11 Correct 5 ms 45520 KB Output is correct
12 Correct 5 ms 45400 KB Output is correct
13 Correct 5 ms 45404 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45580 KB Output is correct
16 Correct 5 ms 45536 KB Output is correct
17 Correct 7 ms 45660 KB Output is correct
18 Correct 8 ms 45816 KB Output is correct
19 Correct 9 ms 45660 KB Output is correct
20 Correct 7 ms 45660 KB Output is correct
21 Correct 8 ms 45844 KB Output is correct
22 Correct 8 ms 45660 KB Output is correct
23 Correct 8 ms 45600 KB Output is correct
24 Correct 193 ms 78448 KB Output is correct
25 Correct 415 ms 82376 KB Output is correct
26 Correct 240 ms 78536 KB Output is correct
27 Correct 361 ms 80124 KB Output is correct
28 Correct 304 ms 79932 KB Output is correct
29 Correct 217 ms 81232 KB Output is correct
30 Correct 586 ms 80312 KB Output is correct
31 Correct 213 ms 71476 KB Output is correct
32 Correct 56 ms 54864 KB Output is correct
33 Correct 353 ms 78416 KB Output is correct
34 Correct 511 ms 80984 KB Output is correct
35 Correct 571 ms 73628 KB Output is correct
36 Correct 564 ms 73668 KB Output is correct
37 Correct 253 ms 81608 KB Output is correct
38 Correct 365 ms 83240 KB Output is correct
39 Correct 417 ms 80504 KB Output is correct
40 Correct 431 ms 81032 KB Output is correct
41 Correct 5 ms 45404 KB Output is correct
42 Correct 631 ms 83372 KB Output is correct
43 Correct 366 ms 81216 KB Output is correct
44 Correct 530 ms 83772 KB Output is correct
45 Correct 592 ms 77376 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45404 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 45404 KB Output is correct
5 Correct 5 ms 45400 KB Output is correct
6 Correct 5 ms 45404 KB Output is correct
7 Correct 5 ms 45684 KB Output is correct
8 Correct 6 ms 45404 KB Output is correct
9 Correct 5 ms 45400 KB Output is correct
10 Correct 6 ms 45404 KB Output is correct
11 Correct 5 ms 45520 KB Output is correct
12 Correct 5 ms 45400 KB Output is correct
13 Correct 5 ms 45404 KB Output is correct
14 Correct 5 ms 45404 KB Output is correct
15 Correct 5 ms 45580 KB Output is correct
16 Correct 5 ms 45536 KB Output is correct
17 Correct 7 ms 45660 KB Output is correct
18 Correct 8 ms 45816 KB Output is correct
19 Correct 9 ms 45660 KB Output is correct
20 Correct 7 ms 45660 KB Output is correct
21 Correct 8 ms 45844 KB Output is correct
22 Correct 8 ms 45660 KB Output is correct
23 Correct 8 ms 45600 KB Output is correct
24 Correct 193 ms 78448 KB Output is correct
25 Correct 415 ms 82376 KB Output is correct
26 Correct 240 ms 78536 KB Output is correct
27 Correct 361 ms 80124 KB Output is correct
28 Correct 304 ms 79932 KB Output is correct
29 Correct 217 ms 81232 KB Output is correct
30 Correct 586 ms 80312 KB Output is correct
31 Correct 213 ms 71476 KB Output is correct
32 Correct 56 ms 54864 KB Output is correct
33 Correct 353 ms 78416 KB Output is correct
34 Correct 511 ms 80984 KB Output is correct
35 Correct 571 ms 73628 KB Output is correct
36 Correct 564 ms 73668 KB Output is correct
37 Correct 253 ms 81608 KB Output is correct
38 Correct 365 ms 83240 KB Output is correct
39 Correct 417 ms 80504 KB Output is correct
40 Correct 431 ms 81032 KB Output is correct
41 Correct 5 ms 45404 KB Output is correct
42 Correct 631 ms 83372 KB Output is correct
43 Correct 366 ms 81216 KB Output is correct
44 Correct 530 ms 83772 KB Output is correct
45 Correct 592 ms 77376 KB Output is correct
46 Correct 1308 ms 209128 KB Output is correct
47 Correct 1952 ms 216900 KB Output is correct
48 Correct 2253 ms 203572 KB Output is correct
49 Correct 2241 ms 203692 KB Output is correct
50 Correct 4003 ms 216800 KB Output is correct
51 Correct 2168 ms 205756 KB Output is correct
52 Correct 3007 ms 213112 KB Output is correct
53 Correct 3738 ms 185532 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 82356 KB Output is correct
2 Correct 406 ms 83236 KB Output is correct
3 Correct 228 ms 82744 KB Output is correct
4 Correct 306 ms 80480 KB Output is correct
5 Correct 6 ms 45400 KB Output is correct
6 Correct 369 ms 83756 KB Output is correct
7 Correct 97 ms 71620 KB Output is correct
8 Correct 68 ms 56656 KB Output is correct
9 Correct 229 ms 83856 KB Output is correct
10 Correct 417 ms 76908 KB Output is correct
11 Correct 204 ms 77632 KB Output is correct
12 Correct 5 ms 45404 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 45404 KB Output is correct
16 Correct 5 ms 45400 KB Output is correct
17 Correct 5 ms 45404 KB Output is correct
18 Correct 5 ms 45684 KB Output is correct
19 Correct 6 ms 45404 KB Output is correct
20 Correct 5 ms 45400 KB Output is correct
21 Correct 6 ms 45404 KB Output is correct
22 Correct 5 ms 45520 KB Output is correct
23 Correct 5 ms 45400 KB Output is correct
24 Correct 5 ms 45404 KB Output is correct
25 Correct 5 ms 45404 KB Output is correct
26 Correct 5 ms 45580 KB Output is correct
27 Correct 5 ms 45536 KB Output is correct
28 Correct 7 ms 45660 KB Output is correct
29 Correct 8 ms 45816 KB Output is correct
30 Correct 9 ms 45660 KB Output is correct
31 Correct 7 ms 45660 KB Output is correct
32 Correct 8 ms 45844 KB Output is correct
33 Correct 8 ms 45660 KB Output is correct
34 Correct 8 ms 45600 KB Output is correct
35 Correct 193 ms 78448 KB Output is correct
36 Correct 415 ms 82376 KB Output is correct
37 Correct 240 ms 78536 KB Output is correct
38 Correct 361 ms 80124 KB Output is correct
39 Correct 304 ms 79932 KB Output is correct
40 Correct 217 ms 81232 KB Output is correct
41 Correct 586 ms 80312 KB Output is correct
42 Correct 213 ms 71476 KB Output is correct
43 Correct 56 ms 54864 KB Output is correct
44 Correct 353 ms 78416 KB Output is correct
45 Correct 511 ms 80984 KB Output is correct
46 Correct 571 ms 73628 KB Output is correct
47 Correct 564 ms 73668 KB Output is correct
48 Correct 253 ms 81608 KB Output is correct
49 Correct 365 ms 83240 KB Output is correct
50 Correct 417 ms 80504 KB Output is correct
51 Correct 431 ms 81032 KB Output is correct
52 Correct 5 ms 45404 KB Output is correct
53 Correct 631 ms 83372 KB Output is correct
54 Correct 366 ms 81216 KB Output is correct
55 Correct 530 ms 83772 KB Output is correct
56 Correct 592 ms 77376 KB Output is correct
57 Correct 256 ms 82152 KB Output is correct
58 Incorrect 360 ms 83904 KB Output isn't correct
59 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 82356 KB Output is correct
2 Correct 406 ms 83236 KB Output is correct
3 Correct 228 ms 82744 KB Output is correct
4 Correct 306 ms 80480 KB Output is correct
5 Correct 6 ms 45400 KB Output is correct
6 Correct 369 ms 83756 KB Output is correct
7 Correct 97 ms 71620 KB Output is correct
8 Correct 68 ms 56656 KB Output is correct
9 Correct 229 ms 83856 KB Output is correct
10 Correct 417 ms 76908 KB Output is correct
11 Correct 204 ms 77632 KB Output is correct
12 Correct 5 ms 45404 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 45404 KB Output is correct
16 Correct 5 ms 45400 KB Output is correct
17 Correct 5 ms 45404 KB Output is correct
18 Correct 5 ms 45684 KB Output is correct
19 Correct 6 ms 45404 KB Output is correct
20 Correct 5 ms 45400 KB Output is correct
21 Correct 6 ms 45404 KB Output is correct
22 Correct 5 ms 45520 KB Output is correct
23 Correct 5 ms 45400 KB Output is correct
24 Correct 5 ms 45404 KB Output is correct
25 Correct 5 ms 45404 KB Output is correct
26 Correct 5 ms 45580 KB Output is correct
27 Correct 5 ms 45536 KB Output is correct
28 Correct 7 ms 45660 KB Output is correct
29 Correct 8 ms 45816 KB Output is correct
30 Correct 9 ms 45660 KB Output is correct
31 Correct 7 ms 45660 KB Output is correct
32 Correct 8 ms 45844 KB Output is correct
33 Correct 8 ms 45660 KB Output is correct
34 Correct 8 ms 45600 KB Output is correct
35 Correct 193 ms 78448 KB Output is correct
36 Correct 415 ms 82376 KB Output is correct
37 Correct 240 ms 78536 KB Output is correct
38 Correct 361 ms 80124 KB Output is correct
39 Correct 304 ms 79932 KB Output is correct
40 Correct 217 ms 81232 KB Output is correct
41 Correct 586 ms 80312 KB Output is correct
42 Correct 213 ms 71476 KB Output is correct
43 Correct 56 ms 54864 KB Output is correct
44 Correct 353 ms 78416 KB Output is correct
45 Correct 511 ms 80984 KB Output is correct
46 Correct 571 ms 73628 KB Output is correct
47 Correct 564 ms 73668 KB Output is correct
48 Correct 253 ms 81608 KB Output is correct
49 Correct 365 ms 83240 KB Output is correct
50 Correct 417 ms 80504 KB Output is correct
51 Correct 431 ms 81032 KB Output is correct
52 Correct 5 ms 45404 KB Output is correct
53 Correct 631 ms 83372 KB Output is correct
54 Correct 366 ms 81216 KB Output is correct
55 Correct 530 ms 83772 KB Output is correct
56 Correct 592 ms 77376 KB Output is correct
57 Correct 1308 ms 209128 KB Output is correct
58 Correct 1952 ms 216900 KB Output is correct
59 Correct 2253 ms 203572 KB Output is correct
60 Correct 2241 ms 203692 KB Output is correct
61 Correct 4003 ms 216800 KB Output is correct
62 Correct 2168 ms 205756 KB Output is correct
63 Correct 3007 ms 213112 KB Output is correct
64 Correct 3738 ms 185532 KB Output is correct
65 Correct 256 ms 82152 KB Output is correct
66 Incorrect 360 ms 83904 KB Output isn't correct
67 Halted 0 ms 0 KB -