Submission #857845

#TimeUsernameProblemLanguageResultExecution timeMemory
857845rxlfd314Two Dishes (JOI19_dishes)C++17
5 / 100
429 ms77240 KiB
#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 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 (stderr)

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:75:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
dishes.cpp: In function 'void print(int, int, int)':
dishes.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...