Submission #1170897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170897		4QT0R	Two Dishes (JOI19_dishes)	C++20	10 / 100	548 ms	32260 KiB

dishes

#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';
}

• Subtask 1: 0 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9