oj.uz

답안 #583583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
583583 2022-06-25T15:56:55 Z Johann Two Dishes (JOI19_dishes) C++14
100 / 100
 5746 ms 141716 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll,ll>
#define vi vector<ll>
#define vpii vector<pii>
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

const ll inf = 1LL << 60;

struct operation {
    ll addopt=0;
    ll maxopt=-inf;
};
struct segtree {
    int size = 1 << 20;
    vector<ll> arr;
    vector<operation> opt;
    ll combine(ll ld, ll rd) {
        return max(ld, rd);
    }
    ll calculate(operation o, ll d) {
        return max(o.maxopt, d + o.addopt);
    }
    operation merge(operation ot, operation ob) { // ot ist das neue, ob ist das alte.
        return { ot.addopt + ob.addopt, max(ot.maxopt, ob.maxopt + ot.addopt) };
    }
    segtree(int N) {
        arr.assign(2*size, 0);
        opt.assign(size, operation());
    }
    void apply(int x, operation & o) {
        arr[x] = calculate(o, arr[x]);
        if (x < size)
            opt[x] = merge(o, opt[x]);
    }
    void push(int x) {
        apply(2 * x, opt[x]);
        apply(2*x+1, opt[x]);
        opt[x] = operation();
    }
    ll query(int l, int r, int x, int lx, int rx) {
        if (l <= lx && rx <= r) { return arr[x]; }
        if (rx <= l || r <= lx) { return -inf; }
        push(x);
        int m = ( lx + rx ) / 2;
        ll lv = query(l, r, 2 * x, lx, m);
        ll rv = query(l, r, 2*x+1, m, rx);
        return combine(lv, rv);
    }
    void apply(int l, int r, operation o, int x, int lx, int rx) { // add or max
        if (l <= lx && rx <= r) { apply(x, o); return; }
        if (rx <= l || r <= lx) { return; }
        push(x);
        int m = ( lx + rx ) / 2;
        apply(l, r, o, 2 * x, lx, m);
        apply(l, r, o, 2*x+1, m, rx);
        arr[x] = combine(arr[2 * x], arr[2*x+1]);
    }
    void apply(int l, int r, operation o) {
        apply(l, r, o, 1, 0, size);
    }
    ll query(int l, int r){
        return query(l, r, 1, 0, size);
    }
};

const int MAXN = 1000100;
ll N[2];
ll A[2][MAXN],T[2][MAXN],P[2][MAXN];
vector<int> rem[MAXN];

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

    cin >> N[0] >> N[1];
    for (int j = 0; j < 2; ++j) {
        for (int i = 0; i < N[j]; ++i) {
            cin >> A[j][i] >> T[j][i] >> P[j][i];
            if (i > 0) A[j][i] += A[j][i-1]; // A ist eine Präfixsumme
            T[j][i] -= A[j][i]; // Wie viel darf ich vom anderen machen, ich noch Punkte bekomme?
        }
    }

    // Segmentbaum auf N[1] aufgebaut
    segtree seg = segtree(N[1]+1);
    // Index shift bei j um 1!
    // init 0th layer:
    ll p1 = 0;
    for (int j = 0; j < N[1]; ++j) {
        if (T[1][j] >= 0) {
            p1 += P[1][j];
            int k = upper_bound(A[0], A[0] + N[0], T[1][j]) - A[0];
            rem[k].push_back(j);
        }
    }
    seg.apply(0, N[1]+1, { p1, -inf });
    // ernst
    for (int i = 0; i < N[0]; ++i) {
        vi cuts;
        for (int j : rem[i]) {
            seg.apply(0, j+1, { - P[1][j], -inf });
            cuts.push_back(j+1);
            // for (int i = 0; i <= N[1]; ++i) cout << seg.query(i, i+1) << " "; cout << endl;
        }
        if (T[0][i] >= 0) {
            ll j = upper_bound(A[1], A[1] + N[1], T[0][i]) - A[1];
            seg.apply(0, j+1, { P[0][i], -inf });
            cuts.push_back(j+1);
            // for (int i = 0; i <= N[1]; ++i) cout << seg.query(i, i+1) << " "; cout << endl;
        }
        for (int x : cuts) {
            ll v = seg.query(0, x);
            seg.apply(x, N[1]+1, { 0, v });
            // for (int i = 0; i <= N[1]; ++i) cout << seg.query(i, i+1) << " "; cout << endl;
        }
    }
    cout << seg.query(0, N[1]+1) << "\n";
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 652 ms 69852 KB Output is correct
2 Correct 688 ms 69652 KB Output is correct
3 Correct 354 ms 67220 KB Output is correct
4 Correct 514 ms 69712 KB Output is correct
5 Correct 31 ms 56600 KB Output is correct
6 Correct 623 ms 68740 KB Output is correct
7 Correct 98 ms 62540 KB Output is correct
8 Correct 280 ms 61400 KB Output is correct
9 Correct 357 ms 67200 KB Output is correct
10 Correct 663 ms 72348 KB Output is correct
11 Correct 310 ms 67300 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 56584 KB Output is correct
2 Correct 31 ms 56588 KB Output is correct
3 Correct 26 ms 56576 KB Output is correct
4 Correct 32 ms 56684 KB Output is correct
5 Correct 26 ms 56592 KB Output is correct
6 Correct 27 ms 56660 KB Output is correct
7 Correct 25 ms 56636 KB Output is correct
8 Correct 24 ms 56596 KB Output is correct
9 Correct 25 ms 56668 KB Output is correct
10 Correct 26 ms 56660 KB Output is correct
11 Correct 25 ms 56660 KB Output is correct
12 Correct 26 ms 56676 KB Output is correct
13 Correct 25 ms 56668 KB Output is correct
14 Correct 27 ms 56660 KB Output is correct
15 Correct 25 ms 56624 KB Output is correct
16 Correct 25 ms 56660 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 56584 KB Output is correct
2 Correct 31 ms 56588 KB Output is correct
3 Correct 26 ms 56576 KB Output is correct
4 Correct 32 ms 56684 KB Output is correct
5 Correct 26 ms 56592 KB Output is correct
6 Correct 27 ms 56660 KB Output is correct
7 Correct 25 ms 56636 KB Output is correct
8 Correct 24 ms 56596 KB Output is correct
9 Correct 25 ms 56668 KB Output is correct
10 Correct 26 ms 56660 KB Output is correct
11 Correct 25 ms 56660 KB Output is correct
12 Correct 26 ms 56676 KB Output is correct
13 Correct 25 ms 56668 KB Output is correct
14 Correct 27 ms 56660 KB Output is correct
15 Correct 25 ms 56624 KB Output is correct
16 Correct 25 ms 56660 KB Output is correct
17 Correct 36 ms 56880 KB Output is correct
18 Correct 31 ms 56916 KB Output is correct
19 Correct 33 ms 56844 KB Output is correct
20 Correct 32 ms 56800 KB Output is correct
21 Correct 31 ms 56872 KB Output is correct
22 Correct 30 ms 56784 KB Output is correct
23 Correct 33 ms 56748 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 56584 KB Output is correct
2 Correct 31 ms 56588 KB Output is correct
3 Correct 26 ms 56576 KB Output is correct
4 Correct 32 ms 56684 KB Output is correct
5 Correct 26 ms 56592 KB Output is correct
6 Correct 27 ms 56660 KB Output is correct
7 Correct 25 ms 56636 KB Output is correct
8 Correct 24 ms 56596 KB Output is correct
9 Correct 25 ms 56668 KB Output is correct
10 Correct 26 ms 56660 KB Output is correct
11 Correct 25 ms 56660 KB Output is correct
12 Correct 26 ms 56676 KB Output is correct
13 Correct 25 ms 56668 KB Output is correct
14 Correct 27 ms 56660 KB Output is correct
15 Correct 25 ms 56624 KB Output is correct
16 Correct 25 ms 56660 KB Output is correct
17 Correct 36 ms 56880 KB Output is correct
18 Correct 31 ms 56916 KB Output is correct
19 Correct 33 ms 56844 KB Output is correct
20 Correct 32 ms 56800 KB Output is correct
21 Correct 31 ms 56872 KB Output is correct
22 Correct 30 ms 56784 KB Output is correct
23 Correct 33 ms 56748 KB Output is correct
24 Correct 430 ms 77156 KB Output is correct
25 Correct 481 ms 79696 KB Output is correct
26 Correct 412 ms 77380 KB Output is correct
27 Correct 539 ms 83000 KB Output is correct
28 Correct 557 ms 78692 KB Output is correct
29 Correct 353 ms 78488 KB Output is correct
30 Correct 920 ms 80632 KB Output is correct
31 Correct 213 ms 68580 KB Output is correct
32 Correct 277 ms 66636 KB Output is correct
33 Correct 550 ms 78884 KB Output is correct
34 Correct 780 ms 79132 KB Output is correct
35 Correct 832 ms 74372 KB Output is correct
36 Correct 825 ms 74268 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 56584 KB Output is correct
2 Correct 31 ms 56588 KB Output is correct
3 Correct 26 ms 56576 KB Output is correct
4 Correct 32 ms 56684 KB Output is correct
5 Correct 26 ms 56592 KB Output is correct
6 Correct 27 ms 56660 KB Output is correct
7 Correct 25 ms 56636 KB Output is correct
8 Correct 24 ms 56596 KB Output is correct
9 Correct 25 ms 56668 KB Output is correct
10 Correct 26 ms 56660 KB Output is correct
11 Correct 25 ms 56660 KB Output is correct
12 Correct 26 ms 56676 KB Output is correct
13 Correct 25 ms 56668 KB Output is correct
14 Correct 27 ms 56660 KB Output is correct
15 Correct 25 ms 56624 KB Output is correct
16 Correct 25 ms 56660 KB Output is correct
17 Correct 36 ms 56880 KB Output is correct
18 Correct 31 ms 56916 KB Output is correct
19 Correct 33 ms 56844 KB Output is correct
20 Correct 32 ms 56800 KB Output is correct
21 Correct 31 ms 56872 KB Output is correct
22 Correct 30 ms 56784 KB Output is correct
23 Correct 33 ms 56748 KB Output is correct
24 Correct 430 ms 77156 KB Output is correct
25 Correct 481 ms 79696 KB Output is correct
26 Correct 412 ms 77380 KB Output is correct
27 Correct 539 ms 83000 KB Output is correct
28 Correct 557 ms 78692 KB Output is correct
29 Correct 353 ms 78488 KB Output is correct
30 Correct 920 ms 80632 KB Output is correct
31 Correct 213 ms 68580 KB Output is correct
32 Correct 277 ms 66636 KB Output is correct
33 Correct 550 ms 78884 KB Output is correct
34 Correct 780 ms 79132 KB Output is correct
35 Correct 832 ms 74372 KB Output is correct
36 Correct 825 ms 74268 KB Output is correct
37 Correct 463 ms 80324 KB Output is correct
38 Correct 543 ms 86004 KB Output is correct
39 Correct 677 ms 83352 KB Output is correct
40 Correct 689 ms 83368 KB Output is correct
41 Correct 25 ms 56660 KB Output is correct
42 Correct 931 ms 83960 KB Output is correct
43 Correct 556 ms 81720 KB Output is correct
44 Correct 796 ms 82032 KB Output is correct
45 Correct 897 ms 77352 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 56584 KB Output is correct
2 Correct 31 ms 56588 KB Output is correct
3 Correct 26 ms 56576 KB Output is correct
4 Correct 32 ms 56684 KB Output is correct
5 Correct 26 ms 56592 KB Output is correct
6 Correct 27 ms 56660 KB Output is correct
7 Correct 25 ms 56636 KB Output is correct
8 Correct 24 ms 56596 KB Output is correct
9 Correct 25 ms 56668 KB Output is correct
10 Correct 26 ms 56660 KB Output is correct
11 Correct 25 ms 56660 KB Output is correct
12 Correct 26 ms 56676 KB Output is correct
13 Correct 25 ms 56668 KB Output is correct
14 Correct 27 ms 56660 KB Output is correct
15 Correct 25 ms 56624 KB Output is correct
16 Correct 25 ms 56660 KB Output is correct
17 Correct 36 ms 56880 KB Output is correct
18 Correct 31 ms 56916 KB Output is correct
19 Correct 33 ms 56844 KB Output is correct
20 Correct 32 ms 56800 KB Output is correct
21 Correct 31 ms 56872 KB Output is correct
22 Correct 30 ms 56784 KB Output is correct
23 Correct 33 ms 56748 KB Output is correct
24 Correct 430 ms 77156 KB Output is correct
25 Correct 481 ms 79696 KB Output is correct
26 Correct 412 ms 77380 KB Output is correct
27 Correct 539 ms 83000 KB Output is correct
28 Correct 557 ms 78692 KB Output is correct
29 Correct 353 ms 78488 KB Output is correct
30 Correct 920 ms 80632 KB Output is correct
31 Correct 213 ms 68580 KB Output is correct
32 Correct 277 ms 66636 KB Output is correct
33 Correct 550 ms 78884 KB Output is correct
34 Correct 780 ms 79132 KB Output is correct
35 Correct 832 ms 74372 KB Output is correct
36 Correct 825 ms 74268 KB Output is correct
37 Correct 463 ms 80324 KB Output is correct
38 Correct 543 ms 86004 KB Output is correct
39 Correct 677 ms 83352 KB Output is correct
40 Correct 689 ms 83368 KB Output is correct
41 Correct 25 ms 56660 KB Output is correct
42 Correct 931 ms 83960 KB Output is correct
43 Correct 556 ms 81720 KB Output is correct
44 Correct 796 ms 82032 KB Output is correct
45 Correct 897 ms 77352 KB Output is correct
46 Correct 2207 ms 112312 KB Output is correct
47 Correct 2736 ms 141516 KB Output is correct
48 Correct 3572 ms 140372 KB Output is correct
49 Correct 3505 ms 140368 KB Output is correct
50 Correct 5720 ms 129800 KB Output is correct
51 Correct 3103 ms 119508 KB Output is correct
52 Correct 4530 ms 119260 KB Output is correct
53 Correct 5574 ms 126524 KB Output is correct

Subtask #7
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 652 ms 69852 KB Output is correct
2 Correct 688 ms 69652 KB Output is correct
3 Correct 354 ms 67220 KB Output is correct
4 Correct 514 ms 69712 KB Output is correct
5 Correct 31 ms 56600 KB Output is correct
6 Correct 623 ms 68740 KB Output is correct
7 Correct 98 ms 62540 KB Output is correct
8 Correct 280 ms 61400 KB Output is correct
9 Correct 357 ms 67200 KB Output is correct
10 Correct 663 ms 72348 KB Output is correct
11 Correct 310 ms 67300 KB Output is correct
12 Correct 27 ms 56584 KB Output is correct
13 Correct 31 ms 56588 KB Output is correct
14 Correct 26 ms 56576 KB Output is correct
15 Correct 32 ms 56684 KB Output is correct
16 Correct 26 ms 56592 KB Output is correct
17 Correct 27 ms 56660 KB Output is correct
18 Correct 25 ms 56636 KB Output is correct
19 Correct 24 ms 56596 KB Output is correct
20 Correct 25 ms 56668 KB Output is correct
21 Correct 26 ms 56660 KB Output is correct
22 Correct 25 ms 56660 KB Output is correct
23 Correct 26 ms 56676 KB Output is correct
24 Correct 25 ms 56668 KB Output is correct
25 Correct 27 ms 56660 KB Output is correct
26 Correct 25 ms 56624 KB Output is correct
27 Correct 25 ms 56660 KB Output is correct
28 Correct 36 ms 56880 KB Output is correct
29 Correct 31 ms 56916 KB Output is correct
30 Correct 33 ms 56844 KB Output is correct
31 Correct 32 ms 56800 KB Output is correct
32 Correct 31 ms 56872 KB Output is correct
33 Correct 30 ms 56784 KB Output is correct
34 Correct 33 ms 56748 KB Output is correct
35 Correct 430 ms 77156 KB Output is correct
36 Correct 481 ms 79696 KB Output is correct
37 Correct 412 ms 77380 KB Output is correct
38 Correct 539 ms 83000 KB Output is correct
39 Correct 557 ms 78692 KB Output is correct
40 Correct 353 ms 78488 KB Output is correct
41 Correct 920 ms 80632 KB Output is correct
42 Correct 213 ms 68580 KB Output is correct
43 Correct 277 ms 66636 KB Output is correct
44 Correct 550 ms 78884 KB Output is correct
45 Correct 780 ms 79132 KB Output is correct
46 Correct 832 ms 74372 KB Output is correct
47 Correct 825 ms 74268 KB Output is correct
48 Correct 463 ms 80324 KB Output is correct
49 Correct 543 ms 86004 KB Output is correct
50 Correct 677 ms 83352 KB Output is correct
51 Correct 689 ms 83368 KB Output is correct
52 Correct 25 ms 56660 KB Output is correct
53 Correct 931 ms 83960 KB Output is correct
54 Correct 556 ms 81720 KB Output is correct
55 Correct 796 ms 82032 KB Output is correct
56 Correct 897 ms 77352 KB Output is correct
57 Correct 492 ms 80804 KB Output is correct
58 Correct 588 ms 86464 KB Output is correct
59 Correct 781 ms 84352 KB Output is correct
60 Correct 759 ms 84296 KB Output is correct
61 Correct 1016 ms 80764 KB Output is correct
62 Correct 26 ms 56660 KB Output is correct
63 Correct 991 ms 83964 KB Output is correct
64 Correct 634 ms 81724 KB Output is correct
65 Correct 817 ms 82016 KB Output is correct
66 Correct 973 ms 77476 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 652 ms 69852 KB Output is correct
2 Correct 688 ms 69652 KB Output is correct
3 Correct 354 ms 67220 KB Output is correct
4 Correct 514 ms 69712 KB Output is correct
5 Correct 31 ms 56600 KB Output is correct
6 Correct 623 ms 68740 KB Output is correct
7 Correct 98 ms 62540 KB Output is correct
8 Correct 280 ms 61400 KB Output is correct
9 Correct 357 ms 67200 KB Output is correct
10 Correct 663 ms 72348 KB Output is correct
11 Correct 310 ms 67300 KB Output is correct
12 Correct 27 ms 56584 KB Output is correct
13 Correct 31 ms 56588 KB Output is correct
14 Correct 26 ms 56576 KB Output is correct
15 Correct 32 ms 56684 KB Output is correct
16 Correct 26 ms 56592 KB Output is correct
17 Correct 27 ms 56660 KB Output is correct
18 Correct 25 ms 56636 KB Output is correct
19 Correct 24 ms 56596 KB Output is correct
20 Correct 25 ms 56668 KB Output is correct
21 Correct 26 ms 56660 KB Output is correct
22 Correct 25 ms 56660 KB Output is correct
23 Correct 26 ms 56676 KB Output is correct
24 Correct 25 ms 56668 KB Output is correct
25 Correct 27 ms 56660 KB Output is correct
26 Correct 25 ms 56624 KB Output is correct
27 Correct 25 ms 56660 KB Output is correct
28 Correct 36 ms 56880 KB Output is correct
29 Correct 31 ms 56916 KB Output is correct
30 Correct 33 ms 56844 KB Output is correct
31 Correct 32 ms 56800 KB Output is correct
32 Correct 31 ms 56872 KB Output is correct
33 Correct 30 ms 56784 KB Output is correct
34 Correct 33 ms 56748 KB Output is correct
35 Correct 430 ms 77156 KB Output is correct
36 Correct 481 ms 79696 KB Output is correct
37 Correct 412 ms 77380 KB Output is correct
38 Correct 539 ms 83000 KB Output is correct
39 Correct 557 ms 78692 KB Output is correct
40 Correct 353 ms 78488 KB Output is correct
41 Correct 920 ms 80632 KB Output is correct
42 Correct 213 ms 68580 KB Output is correct
43 Correct 277 ms 66636 KB Output is correct
44 Correct 550 ms 78884 KB Output is correct
45 Correct 780 ms 79132 KB Output is correct
46 Correct 832 ms 74372 KB Output is correct
47 Correct 825 ms 74268 KB Output is correct
48 Correct 463 ms 80324 KB Output is correct
49 Correct 543 ms 86004 KB Output is correct
50 Correct 677 ms 83352 KB Output is correct
51 Correct 689 ms 83368 KB Output is correct
52 Correct 25 ms 56660 KB Output is correct
53 Correct 931 ms 83960 KB Output is correct
54 Correct 556 ms 81720 KB Output is correct
55 Correct 796 ms 82032 KB Output is correct
56 Correct 897 ms 77352 KB Output is correct
57 Correct 2207 ms 112312 KB Output is correct
58 Correct 2736 ms 141516 KB Output is correct
59 Correct 3572 ms 140372 KB Output is correct
60 Correct 3505 ms 140368 KB Output is correct
61 Correct 5720 ms 129800 KB Output is correct
62 Correct 3103 ms 119508 KB Output is correct
63 Correct 4530 ms 119260 KB Output is correct
64 Correct 5574 ms 126524 KB Output is correct
65 Correct 492 ms 80804 KB Output is correct
66 Correct 588 ms 86464 KB Output is correct
67 Correct 781 ms 84352 KB Output is correct
68 Correct 759 ms 84296 KB Output is correct
69 Correct 1016 ms 80764 KB Output is correct
70 Correct 26 ms 56660 KB Output is correct
71 Correct 991 ms 83964 KB Output is correct
72 Correct 634 ms 81724 KB Output is correct
73 Correct 817 ms 82016 KB Output is correct
74 Correct 973 ms 77476 KB Output is correct
75 Correct 2245 ms 112676 KB Output is correct
76 Correct 2893 ms 141716 KB Output is correct
77 Correct 3664 ms 140000 KB Output is correct
78 Correct 3657 ms 139884 KB Output is correct
79 Correct 5746 ms 129348 KB Output is correct
80 Correct 3182 ms 118928 KB Output is correct
81 Correct 4132 ms 117472 KB Output is correct
82 Correct 5553 ms 126032 KB Output is correct
83 Correct 5464 ms 125236 KB Output is correct