Submission #1170897

#TimeUsernameProblemLanguageResultExecution timeMemory
11708974QT0RTwo Dishes (JOI19_dishes)C++20
10 / 100
548 ms32260 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll dp[2002][2002];
ll sum_pref[2][2002];
ll times[2][2002];
ll req[2][2002];
ll bonus[2][2002];

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

	ll n,m;
	cin >> n >> m;
	for (ll i = 1; i<=n; i++){
		cin >> times[0][i] >> req[0][i] >> bonus[0][i];
		sum_pref[0][i]=sum_pref[0][i-1]+times[0][i];
	} 
	for (ll i = 1; i<=m; i++){
		cin >> times[1][i] >> req[1][i] >> bonus[1][i];
		sum_pref[1][i]=sum_pref[1][i-1]+times[1][i];
	}
	for (ll i = 1; i<=m; i++){
		dp[0][i]=dp[0][i-1]+(sum_pref[1][i]<=req[1][i]?bonus[1][i]:0);
	}
	for (ll i = 1; i<=n; i++){
		dp[i][0]=dp[i-1][0]+(sum_pref[0][i]<=req[0][i]?bonus[0][i]:0);
		for (ll j = 1; j<=m; j++){
			dp[i][j]=max(dp[i-1][j]+((sum_pref[0][i]+sum_pref[1][j])<=req[0][i]?bonus[0][i]:0),
						dp[i][j-1]+((sum_pref[0][i]+sum_pref[1][j])<=req[1][j]?bonus[1][j]:0));
		}
	}
	cout << dp[n][m] << '\n';
}
#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...