Submission #1170990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170990		mateuszwes	Two Dishes (JOI19_dishes)	C++20	0 / 100	996 ms	28928 KiB

dishes

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pii pair<int,int>
#define pl pair<ll,ll>
#define F first
#define S second
#define pq priority_queue
#define all(x) x.begin(), x.end()
#define deb(x) cout << #x << " = " << x << '\n';
#define deb2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << '\n';

constexpr int M = 1e9+7;
constexpr int N = 2e5+7;
constexpr bool debug = 0;

int dp[2007][2007];
ll spref1[N];
ll spref2[N];
ll best[2007];

struct el{
	ll a1, s1, p1;
};

el d1[N], d2[N];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> d1[i].a1 >> d1[i].s1 >> d1[i].p1;
		spref1[i+1] = spref1[i]+d1[i].a1;
	}
	for(int i = 0; i < m; i++){
		cin >> d2[i].a1 >> d2[i].s1 >> d2[i].p1;
		spref2[i+1] = spref2[i]+d2[i].a1;
	}

	dp[0][0] = 0;
	for(int i = 1; i <= n; i++){
		dp[i][0] = dp[i-1][0];
		if(spref1[i] <= d1[i].s1) dp[i][0]++;
		for(int j = 1; j <= m; j++){
			int c1 = dp[i][j-1];
			ll ob = spref1[i]+spref2[j-1];
			if(ob <= d2[j-1].s1) c1++;

			int c2 = dp[i-1][j];
			ob = spref1[i-1]+spref2[j];
			if(ob <= d2[i-1].s1) c2++;
			dp[i][j] = max(c1, c2);
		}
	}

	cout << dp[n][m];
	return 0;
}

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