oj.uz

Submission #522612

# Submission time Handle Problem Language Result Execution time Memory
522612 2022-02-05T09:30:08 Z blue Two Dishes (JOI19_dishes) C++17
10 / 100
 485 ms 1048580 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Runtime error 485 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -