답안 #789716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
789716	2023-07-21T20:18:16 Z	someone	Two Dishes (JOI19_dishes)	C++14	74 / 100	6164 ms	233752 KB

dishes

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int M = 1 << 20, N = 2 * M, INF = 1e18 + 42;

int n, m, maxi[N], tag[N], sum[N];
vector<int> a[2], s[2], p[2], pos[2];

void add(int i, int pt) {
    i = max(i, 0ll);
    i += M;
    while(i) {
        sum[i] += pt;
        i >>= 1;
    }
}

int getSum(int i) {
    if(i == -1) return 0;
    i += M;
    int ans = sum[i];
    while(i) {
        if(i & 1) ans += sum[i-1];
        i >>= 1;
    }
    return ans;
}

void applyOp(int i, int add) {
    tag[i] += add;
    maxi[i] += add;
}

void propage(int i) {
    applyOp(i*2, tag[i]);
    applyOp(i*2+1, tag[i]);
    tag[i] = 0;
}

int update(int i, int deb, int fin, int l, int r, int add) {
    if(r <= deb || fin <= l)
        return 0;
    if(l <= deb && fin <= r) {
        applyOp(i, add);
        return maxi[i];
    }
    propage(i);
    int mid = ((deb + fin) >> 1);
    int ans = max(update(i*2, deb, mid, l, r, add),
                  update(i*2+1, mid, fin, l, r, add));
    maxi[i] = max(maxi[i*2], maxi[i*2+1]);
    return ans;
}

int solve() {
    for(int i = 0; i < N; i++)
        maxi[i] = tag[i] = sum[i] = 0;

    vector<int> ver[M];
    for(int i = 1; i <= m; i++)
        if(pos[1][i] >= 0)
            ver[pos[1][i]].push_back(i);

    int ans = 0;
    for(int i = n; i >= 0; i--) {
        for(int j : ver[i]) {
            add(j, p[1][j]);
            update(1, 0, M, j, M, p[1][j]);
        }
        int dp = update(1, 0, M, pos[0][i], M, 0);
        ans = max(ans, dp - getSum(pos[0][i]));
        int val = update(1, 0, M, pos[0][i], pos[0][i]+1, 0);
        update(1, 0, M, pos[0][i], pos[0][i]+1, -val);
        update(1, 0, M, pos[0][i], pos[0][i]+1, dp);
        update(1, 0, M, 0, pos[0][i]+1, p[0][i]);
    }
    return ans;
}

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

    cin >> n >> m;
    int sz[] = {n+1, m+1};
    for(int i = 0; i < 2; i++) {
        a[i].resize(sz[i]);
        s[i].resize(sz[i]);
        p[i].resize(sz[i]);
        pos[i].resize(sz[i]);
    }

    for(int i = 1; i <= n; i++)
        cin >> a[0][i] >> s[0][i] >> p[0][i];
    for(int i = 1; i <= m; i++)
        cin >> a[1][i] >> s[1][i] >> p[1][i];
    for(int i = 1; i <= n; i++)
        a[0][i] += a[0][i-1];
    for(int i = 1; i <= m; i++)
        a[1][i] += a[1][i-1];

    for(int i = 0; i <= n; i++)
        pos[0][i] = (int)(upper_bound(a[1].begin(), a[1].end(), s[0][i] - a[0][i]) - a[1].begin())-1;
    for(int i = 0; i <= m; i++)
        pos[1][i] = (int)(upper_bound(a[0].begin(), a[0].end(), s[1][i] - a[1][i]) - a[0].begin())-1;


    int ans = solve();
    swap(n, m);
    swap(a[0], a[1]);
    swap(s[0], s[1]);
    swap(p[0], p[1]);
    swap(pos[0], pos[1]);
    cout << max(ans, solve()) << '\n';
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	621 ms	92852 KB	Output is correct
2	Correct	640 ms	91592 KB	Output is correct
3	Correct	583 ms	91668 KB	Output is correct
4	Correct	463 ms	91332 KB	Output is correct
5	Correct	32 ms	74068 KB	Output is correct
6	Correct	611 ms	89952 KB	Output is correct
7	Correct	306 ms	82632 KB	Output is correct
8	Correct	361 ms	82628 KB	Output is correct
9	Correct	580 ms	91436 KB	Output is correct
10	Correct	637 ms	94340 KB	Output is correct
11	Correct	550 ms	91596 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	74128 KB	Output is correct
2	Correct	33 ms	74152 KB	Output is correct
3	Correct	33 ms	74056 KB	Output is correct
4	Correct	35 ms	74144 KB	Output is correct
5	Correct	35 ms	74096 KB	Output is correct
6	Correct	33 ms	74188 KB	Output is correct
7	Correct	33 ms	74164 KB	Output is correct
8	Correct	33 ms	74068 KB	Output is correct
9	Correct	33 ms	74188 KB	Output is correct
10	Correct	33 ms	74068 KB	Output is correct
11	Correct	33 ms	74128 KB	Output is correct
12	Correct	33 ms	74132 KB	Output is correct
13	Correct	35 ms	74160 KB	Output is correct
14	Correct	33 ms	74060 KB	Output is correct
15	Correct	33 ms	74144 KB	Output is correct
16	Correct	32 ms	74092 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	74128 KB	Output is correct
2	Correct	33 ms	74152 KB	Output is correct
3	Correct	33 ms	74056 KB	Output is correct
4	Correct	35 ms	74144 KB	Output is correct
5	Correct	35 ms	74096 KB	Output is correct
6	Correct	33 ms	74188 KB	Output is correct
7	Correct	33 ms	74164 KB	Output is correct
8	Correct	33 ms	74068 KB	Output is correct
9	Correct	33 ms	74188 KB	Output is correct
10	Correct	33 ms	74068 KB	Output is correct
11	Correct	33 ms	74128 KB	Output is correct
12	Correct	33 ms	74132 KB	Output is correct
13	Correct	35 ms	74160 KB	Output is correct
14	Correct	33 ms	74060 KB	Output is correct
15	Correct	33 ms	74144 KB	Output is correct
16	Correct	32 ms	74092 KB	Output is correct
17	Correct	38 ms	74276 KB	Output is correct
18	Correct	38 ms	74204 KB	Output is correct
19	Correct	40 ms	74444 KB	Output is correct
20	Correct	37 ms	74380 KB	Output is correct
21	Correct	39 ms	74300 KB	Output is correct
22	Correct	41 ms	74372 KB	Output is correct
23	Correct	44 ms	74452 KB	Output is correct

Subtask #4
39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	74128 KB	Output is correct
2	Correct	33 ms	74152 KB	Output is correct
3	Correct	33 ms	74056 KB	Output is correct
4	Correct	35 ms	74144 KB	Output is correct
5	Correct	35 ms	74096 KB	Output is correct
6	Correct	33 ms	74188 KB	Output is correct
7	Correct	33 ms	74164 KB	Output is correct
8	Correct	33 ms	74068 KB	Output is correct
9	Correct	33 ms	74188 KB	Output is correct
10	Correct	33 ms	74068 KB	Output is correct
11	Correct	33 ms	74128 KB	Output is correct
12	Correct	33 ms	74132 KB	Output is correct
13	Correct	35 ms	74160 KB	Output is correct
14	Correct	33 ms	74060 KB	Output is correct
15	Correct	33 ms	74144 KB	Output is correct
16	Correct	32 ms	74092 KB	Output is correct
17	Correct	38 ms	74276 KB	Output is correct
18	Correct	38 ms	74204 KB	Output is correct
19	Correct	40 ms	74444 KB	Output is correct
20	Correct	37 ms	74380 KB	Output is correct
21	Correct	39 ms	74300 KB	Output is correct
22	Correct	41 ms	74372 KB	Output is correct
23	Correct	44 ms	74452 KB	Output is correct
24	Correct	446 ms	90812 KB	Output is correct
25	Correct	543 ms	90824 KB	Output is correct
26	Correct	504 ms	94780 KB	Output is correct
27	Correct	502 ms	94796 KB	Output is correct
28	Correct	594 ms	91868 KB	Output is correct
29	Correct	570 ms	92264 KB	Output is correct
30	Correct	852 ms	92852 KB	Output is correct
31	Correct	299 ms	83116 KB	Output is correct
32	Correct	348 ms	83112 KB	Output is correct
33	Correct	512 ms	90980 KB	Output is correct
34	Correct	764 ms	91956 KB	Output is correct
35	Correct	836 ms	92020 KB	Output is correct
36	Correct	832 ms	91856 KB	Output is correct

Subtask #5
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	74128 KB	Output is correct
2	Correct	33 ms	74152 KB	Output is correct
3	Correct	33 ms	74056 KB	Output is correct
4	Correct	35 ms	74144 KB	Output is correct
5	Correct	35 ms	74096 KB	Output is correct
6	Correct	33 ms	74188 KB	Output is correct
7	Correct	33 ms	74164 KB	Output is correct
8	Correct	33 ms	74068 KB	Output is correct
9	Correct	33 ms	74188 KB	Output is correct
10	Correct	33 ms	74068 KB	Output is correct
11	Correct	33 ms	74128 KB	Output is correct
12	Correct	33 ms	74132 KB	Output is correct
13	Correct	35 ms	74160 KB	Output is correct
14	Correct	33 ms	74060 KB	Output is correct
15	Correct	33 ms	74144 KB	Output is correct
16	Correct	32 ms	74092 KB	Output is correct
17	Correct	38 ms	74276 KB	Output is correct
18	Correct	38 ms	74204 KB	Output is correct
19	Correct	40 ms	74444 KB	Output is correct
20	Correct	37 ms	74380 KB	Output is correct
21	Correct	39 ms	74300 KB	Output is correct
22	Correct	41 ms	74372 KB	Output is correct
23	Correct	44 ms	74452 KB	Output is correct
24	Correct	446 ms	90812 KB	Output is correct
25	Correct	543 ms	90824 KB	Output is correct
26	Correct	504 ms	94780 KB	Output is correct
27	Correct	502 ms	94796 KB	Output is correct
28	Correct	594 ms	91868 KB	Output is correct
29	Correct	570 ms	92264 KB	Output is correct
30	Correct	852 ms	92852 KB	Output is correct
31	Correct	299 ms	83116 KB	Output is correct
32	Correct	348 ms	83112 KB	Output is correct
33	Correct	512 ms	90980 KB	Output is correct
34	Correct	764 ms	91956 KB	Output is correct
35	Correct	836 ms	92020 KB	Output is correct
36	Correct	832 ms	91856 KB	Output is correct
37	Correct	534 ms	94816 KB	Output is correct
38	Correct	512 ms	94652 KB	Output is correct
39	Correct	656 ms	94904 KB	Output is correct
40	Correct	659 ms	94968 KB	Output is correct
41	Correct	33 ms	74068 KB	Output is correct
42	Correct	862 ms	92548 KB	Output is correct
43	Correct	516 ms	90184 KB	Output is correct
44	Correct	760 ms	91136 KB	Output is correct
45	Correct	854 ms	91456 KB	Output is correct

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	74128 KB	Output is correct
2	Correct	33 ms	74152 KB	Output is correct
3	Correct	33 ms	74056 KB	Output is correct
4	Correct	35 ms	74144 KB	Output is correct
5	Correct	35 ms	74096 KB	Output is correct
6	Correct	33 ms	74188 KB	Output is correct
7	Correct	33 ms	74164 KB	Output is correct
8	Correct	33 ms	74068 KB	Output is correct
9	Correct	33 ms	74188 KB	Output is correct
10	Correct	33 ms	74068 KB	Output is correct
11	Correct	33 ms	74128 KB	Output is correct
12	Correct	33 ms	74132 KB	Output is correct
13	Correct	35 ms	74160 KB	Output is correct
14	Correct	33 ms	74060 KB	Output is correct
15	Correct	33 ms	74144 KB	Output is correct
16	Correct	32 ms	74092 KB	Output is correct
17	Correct	38 ms	74276 KB	Output is correct
18	Correct	38 ms	74204 KB	Output is correct
19	Correct	40 ms	74444 KB	Output is correct
20	Correct	37 ms	74380 KB	Output is correct
21	Correct	39 ms	74300 KB	Output is correct
22	Correct	41 ms	74372 KB	Output is correct
23	Correct	44 ms	74452 KB	Output is correct
24	Correct	446 ms	90812 KB	Output is correct
25	Correct	543 ms	90824 KB	Output is correct
26	Correct	504 ms	94780 KB	Output is correct
27	Correct	502 ms	94796 KB	Output is correct
28	Correct	594 ms	91868 KB	Output is correct
29	Correct	570 ms	92264 KB	Output is correct
30	Correct	852 ms	92852 KB	Output is correct
31	Correct	299 ms	83116 KB	Output is correct
32	Correct	348 ms	83112 KB	Output is correct
33	Correct	512 ms	90980 KB	Output is correct
34	Correct	764 ms	91956 KB	Output is correct
35	Correct	836 ms	92020 KB	Output is correct
36	Correct	832 ms	91856 KB	Output is correct
37	Correct	534 ms	94816 KB	Output is correct
38	Correct	512 ms	94652 KB	Output is correct
39	Correct	656 ms	94904 KB	Output is correct
40	Correct	659 ms	94968 KB	Output is correct
41	Correct	33 ms	74068 KB	Output is correct
42	Correct	862 ms	92548 KB	Output is correct
43	Correct	516 ms	90184 KB	Output is correct
44	Correct	760 ms	91136 KB	Output is correct
45	Correct	854 ms	91456 KB	Output is correct
46	Correct	2501 ms	168612 KB	Output is correct
47	Correct	2511 ms	233752 KB	Output is correct
48	Correct	3303 ms	224172 KB	Output is correct
49	Correct	3219 ms	224420 KB	Output is correct
50	Correct	6164 ms	227552 KB	Output is correct
51	Correct	3280 ms	213332 KB	Output is correct
52	Correct	4769 ms	218660 KB	Output is correct
53	Correct	5737 ms	196084 KB	Output is correct

Subtask #7
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	621 ms	92852 KB	Output is correct
2	Correct	640 ms	91592 KB	Output is correct
3	Correct	583 ms	91668 KB	Output is correct
4	Correct	463 ms	91332 KB	Output is correct
5	Correct	32 ms	74068 KB	Output is correct
6	Correct	611 ms	89952 KB	Output is correct
7	Correct	306 ms	82632 KB	Output is correct
8	Correct	361 ms	82628 KB	Output is correct
9	Correct	580 ms	91436 KB	Output is correct
10	Correct	637 ms	94340 KB	Output is correct
11	Correct	550 ms	91596 KB	Output is correct
12	Correct	33 ms	74128 KB	Output is correct
13	Correct	33 ms	74152 KB	Output is correct
14	Correct	33 ms	74056 KB	Output is correct
15	Correct	35 ms	74144 KB	Output is correct
16	Correct	35 ms	74096 KB	Output is correct
17	Correct	33 ms	74188 KB	Output is correct
18	Correct	33 ms	74164 KB	Output is correct
19	Correct	33 ms	74068 KB	Output is correct
20	Correct	33 ms	74188 KB	Output is correct
21	Correct	33 ms	74068 KB	Output is correct
22	Correct	33 ms	74128 KB	Output is correct
23	Correct	33 ms	74132 KB	Output is correct
24	Correct	35 ms	74160 KB	Output is correct
25	Correct	33 ms	74060 KB	Output is correct
26	Correct	33 ms	74144 KB	Output is correct
27	Correct	32 ms	74092 KB	Output is correct
28	Correct	38 ms	74276 KB	Output is correct
29	Correct	38 ms	74204 KB	Output is correct
30	Correct	40 ms	74444 KB	Output is correct
31	Correct	37 ms	74380 KB	Output is correct
32	Correct	39 ms	74300 KB	Output is correct
33	Correct	41 ms	74372 KB	Output is correct
34	Correct	44 ms	74452 KB	Output is correct
35	Correct	446 ms	90812 KB	Output is correct
36	Correct	543 ms	90824 KB	Output is correct
37	Correct	504 ms	94780 KB	Output is correct
38	Correct	502 ms	94796 KB	Output is correct
39	Correct	594 ms	91868 KB	Output is correct
40	Correct	570 ms	92264 KB	Output is correct
41	Correct	852 ms	92852 KB	Output is correct
42	Correct	299 ms	83116 KB	Output is correct
43	Correct	348 ms	83112 KB	Output is correct
44	Correct	512 ms	90980 KB	Output is correct
45	Correct	764 ms	91956 KB	Output is correct
46	Correct	836 ms	92020 KB	Output is correct
47	Correct	832 ms	91856 KB	Output is correct
48	Correct	534 ms	94816 KB	Output is correct
49	Correct	512 ms	94652 KB	Output is correct
50	Correct	656 ms	94904 KB	Output is correct
51	Correct	659 ms	94968 KB	Output is correct
52	Correct	33 ms	74068 KB	Output is correct
53	Correct	862 ms	92548 KB	Output is correct
54	Correct	516 ms	90184 KB	Output is correct
55	Correct	760 ms	91136 KB	Output is correct
56	Correct	854 ms	91456 KB	Output is correct
57	Incorrect	553 ms	92960 KB	Output isn't correct
58	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	621 ms	92852 KB	Output is correct
2	Correct	640 ms	91592 KB	Output is correct
3	Correct	583 ms	91668 KB	Output is correct
4	Correct	463 ms	91332 KB	Output is correct
5	Correct	32 ms	74068 KB	Output is correct
6	Correct	611 ms	89952 KB	Output is correct
7	Correct	306 ms	82632 KB	Output is correct
8	Correct	361 ms	82628 KB	Output is correct
9	Correct	580 ms	91436 KB	Output is correct
10	Correct	637 ms	94340 KB	Output is correct
11	Correct	550 ms	91596 KB	Output is correct
12	Correct	33 ms	74128 KB	Output is correct
13	Correct	33 ms	74152 KB	Output is correct
14	Correct	33 ms	74056 KB	Output is correct
15	Correct	35 ms	74144 KB	Output is correct
16	Correct	35 ms	74096 KB	Output is correct
17	Correct	33 ms	74188 KB	Output is correct
18	Correct	33 ms	74164 KB	Output is correct
19	Correct	33 ms	74068 KB	Output is correct
20	Correct	33 ms	74188 KB	Output is correct
21	Correct	33 ms	74068 KB	Output is correct
22	Correct	33 ms	74128 KB	Output is correct
23	Correct	33 ms	74132 KB	Output is correct
24	Correct	35 ms	74160 KB	Output is correct
25	Correct	33 ms	74060 KB	Output is correct
26	Correct	33 ms	74144 KB	Output is correct
27	Correct	32 ms	74092 KB	Output is correct
28	Correct	38 ms	74276 KB	Output is correct
29	Correct	38 ms	74204 KB	Output is correct
30	Correct	40 ms	74444 KB	Output is correct
31	Correct	37 ms	74380 KB	Output is correct
32	Correct	39 ms	74300 KB	Output is correct
33	Correct	41 ms	74372 KB	Output is correct
34	Correct	44 ms	74452 KB	Output is correct
35	Correct	446 ms	90812 KB	Output is correct
36	Correct	543 ms	90824 KB	Output is correct
37	Correct	504 ms	94780 KB	Output is correct
38	Correct	502 ms	94796 KB	Output is correct
39	Correct	594 ms	91868 KB	Output is correct
40	Correct	570 ms	92264 KB	Output is correct
41	Correct	852 ms	92852 KB	Output is correct
42	Correct	299 ms	83116 KB	Output is correct
43	Correct	348 ms	83112 KB	Output is correct
44	Correct	512 ms	90980 KB	Output is correct
45	Correct	764 ms	91956 KB	Output is correct
46	Correct	836 ms	92020 KB	Output is correct
47	Correct	832 ms	91856 KB	Output is correct
48	Correct	534 ms	94816 KB	Output is correct
49	Correct	512 ms	94652 KB	Output is correct
50	Correct	656 ms	94904 KB	Output is correct
51	Correct	659 ms	94968 KB	Output is correct
52	Correct	33 ms	74068 KB	Output is correct
53	Correct	862 ms	92548 KB	Output is correct
54	Correct	516 ms	90184 KB	Output is correct
55	Correct	760 ms	91136 KB	Output is correct
56	Correct	854 ms	91456 KB	Output is correct
57	Correct	2501 ms	168612 KB	Output is correct
58	Correct	2511 ms	233752 KB	Output is correct
59	Correct	3303 ms	224172 KB	Output is correct
60	Correct	3219 ms	224420 KB	Output is correct
61	Correct	6164 ms	227552 KB	Output is correct
62	Correct	3280 ms	213332 KB	Output is correct
63	Correct	4769 ms	218660 KB	Output is correct
64	Correct	5737 ms	196084 KB	Output is correct
65	Incorrect	553 ms	92960 KB	Output isn't correct
66	Halted	0 ms	0 KB	-

답안 #789716

Compilation message