답안 #522612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522612	2022-02-05T09:30:08 Z	blue	Two Dishes (JOI19_dishes)	C++17	10 / 100	485 ms	1048580 KB

dishes

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
using namespace std;

#define sz(x) int(x.size())
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

const int mx = 1'000'000;
const ll INF = 1'000'000'000'000'000'000LL;

int N, M;
vll A(1+mx), S(1+mx), P(1+mx);
vll B(1+mx), T(1+mx), Q(1+mx);

vll Asum(1+mx, 0);
vll Bsum(1+mx, 0);




struct delta
{
	int p;
	ll v;
};

bool operator < (delta A, delta B)
{
	if(A.p == B.p) return A.v < B.v;
	return A.p < B.p;
}




int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	for(int i = 1; i <= N; i++)
	{
		cin >> A[i] >> S[i] >> P[i];
		Asum[i] = Asum[i-1] + A[i];
	}

	for(int j = 1; j <= M; j++)
	{
		cin >> B[j] >> T[j] >> Q[j];
		Bsum[j] = Bsum[j-1] + B[j];
	}


	vvll DP(1+N, vll(1+M, -INF));
	DP[0][0] = 0;

	for(int i = 0; i <= N; i++)
	{
		for(int j = 0; j <= M; j++)
		{
			if(i != 0)
			{
				DP[i][j] = max(DP[i][j], DP[i-1][j] + (Asum[i] + Bsum[j] <= S[i] ? P[i] : 0));
			}
			if(j != 0)
			{
				DP[i][j] = max(DP[i][j], DP[i][j-1] + (Asum[i] + Bsum[j] <= T[j] ? Q[j] : 0));
			}
		}
	}

	cout << DP[N][M] << '\n';
}

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	485 ms	1048580 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	62924 KB	Output is correct
2	Correct	27 ms	62964 KB	Output is correct
3	Correct	26 ms	63044 KB	Output is correct
4	Correct	26 ms	62924 KB	Output is correct
5	Correct	25 ms	62848 KB	Output is correct
6	Correct	25 ms	63004 KB	Output is correct
7	Correct	25 ms	62864 KB	Output is correct
8	Correct	25 ms	62912 KB	Output is correct
9	Correct	26 ms	62840 KB	Output is correct
10	Correct	27 ms	62852 KB	Output is correct
11	Correct	28 ms	62956 KB	Output is correct
12	Correct	25 ms	62964 KB	Output is correct
13	Correct	26 ms	62924 KB	Output is correct
14	Correct	25 ms	62904 KB	Output is correct
15	Correct	27 ms	63044 KB	Output is correct
16	Correct	25 ms	62936 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	62924 KB	Output is correct
2	Correct	27 ms	62964 KB	Output is correct
3	Correct	26 ms	63044 KB	Output is correct
4	Correct	26 ms	62924 KB	Output is correct
5	Correct	25 ms	62848 KB	Output is correct
6	Correct	25 ms	63004 KB	Output is correct
7	Correct	25 ms	62864 KB	Output is correct
8	Correct	25 ms	62912 KB	Output is correct
9	Correct	26 ms	62840 KB	Output is correct
10	Correct	27 ms	62852 KB	Output is correct
11	Correct	28 ms	62956 KB	Output is correct
12	Correct	25 ms	62964 KB	Output is correct
13	Correct	26 ms	62924 KB	Output is correct
14	Correct	25 ms	62904 KB	Output is correct
15	Correct	27 ms	63044 KB	Output is correct
16	Correct	25 ms	62936 KB	Output is correct
17	Correct	70 ms	94456 KB	Output is correct
18	Correct	63 ms	94404 KB	Output is correct
19	Correct	68 ms	94392 KB	Output is correct
20	Correct	64 ms	92200 KB	Output is correct
21	Correct	65 ms	93284 KB	Output is correct
22	Correct	65 ms	94356 KB	Output is correct
23	Correct	76 ms	94404 KB	Output is correct

Subtask #4
0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	62924 KB	Output is correct
2	Correct	27 ms	62964 KB	Output is correct
3	Correct	26 ms	63044 KB	Output is correct
4	Correct	26 ms	62924 KB	Output is correct
5	Correct	25 ms	62848 KB	Output is correct
6	Correct	25 ms	63004 KB	Output is correct
7	Correct	25 ms	62864 KB	Output is correct
8	Correct	25 ms	62912 KB	Output is correct
9	Correct	26 ms	62840 KB	Output is correct
10	Correct	27 ms	62852 KB	Output is correct
11	Correct	28 ms	62956 KB	Output is correct
12	Correct	25 ms	62964 KB	Output is correct
13	Correct	26 ms	62924 KB	Output is correct
14	Correct	25 ms	62904 KB	Output is correct
15	Correct	27 ms	63044 KB	Output is correct
16	Correct	25 ms	62936 KB	Output is correct
17	Correct	70 ms	94456 KB	Output is correct
18	Correct	63 ms	94404 KB	Output is correct
19	Correct	68 ms	94392 KB	Output is correct
20	Correct	64 ms	92200 KB	Output is correct
21	Correct	65 ms	93284 KB	Output is correct
22	Correct	65 ms	94356 KB	Output is correct
23	Correct	76 ms	94404 KB	Output is correct
24	Runtime error	479 ms	1048580 KB	Execution killed with signal 9
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	62924 KB	Output is correct
2	Correct	27 ms	62964 KB	Output is correct
3	Correct	26 ms	63044 KB	Output is correct
4	Correct	26 ms	62924 KB	Output is correct
5	Correct	25 ms	62848 KB	Output is correct
6	Correct	25 ms	63004 KB	Output is correct
7	Correct	25 ms	62864 KB	Output is correct
8	Correct	25 ms	62912 KB	Output is correct
9	Correct	26 ms	62840 KB	Output is correct
10	Correct	27 ms	62852 KB	Output is correct
11	Correct	28 ms	62956 KB	Output is correct
12	Correct	25 ms	62964 KB	Output is correct
13	Correct	26 ms	62924 KB	Output is correct
14	Correct	25 ms	62904 KB	Output is correct
15	Correct	27 ms	63044 KB	Output is correct
16	Correct	25 ms	62936 KB	Output is correct
17	Correct	70 ms	94456 KB	Output is correct
18	Correct	63 ms	94404 KB	Output is correct
19	Correct	68 ms	94392 KB	Output is correct
20	Correct	64 ms	92200 KB	Output is correct
21	Correct	65 ms	93284 KB	Output is correct
22	Correct	65 ms	94356 KB	Output is correct
23	Correct	76 ms	94404 KB	Output is correct
24	Runtime error	479 ms	1048580 KB	Execution killed with signal 9
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	62924 KB	Output is correct
2	Correct	27 ms	62964 KB	Output is correct
3	Correct	26 ms	63044 KB	Output is correct
4	Correct	26 ms	62924 KB	Output is correct
5	Correct	25 ms	62848 KB	Output is correct
6	Correct	25 ms	63004 KB	Output is correct
7	Correct	25 ms	62864 KB	Output is correct
8	Correct	25 ms	62912 KB	Output is correct
9	Correct	26 ms	62840 KB	Output is correct
10	Correct	27 ms	62852 KB	Output is correct
11	Correct	28 ms	62956 KB	Output is correct
12	Correct	25 ms	62964 KB	Output is correct
13	Correct	26 ms	62924 KB	Output is correct
14	Correct	25 ms	62904 KB	Output is correct
15	Correct	27 ms	63044 KB	Output is correct
16	Correct	25 ms	62936 KB	Output is correct
17	Correct	70 ms	94456 KB	Output is correct
18	Correct	63 ms	94404 KB	Output is correct
19	Correct	68 ms	94392 KB	Output is correct
20	Correct	64 ms	92200 KB	Output is correct
21	Correct	65 ms	93284 KB	Output is correct
22	Correct	65 ms	94356 KB	Output is correct
23	Correct	76 ms	94404 KB	Output is correct
24	Runtime error	479 ms	1048580 KB	Execution killed with signal 9
25	Halted	0 ms	0 KB	-

Subtask #7
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	485 ms	1048580 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	485 ms	1048580 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

답안 #522612

Compilation message