Submission #1170996

#TimeUsernameProblemLanguageResultExecution timeMemory
1170996mateuszwesTwo Dishes (JOI19_dishes)C++20
0 / 100
1058 ms28912 KiB
#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-1].s1) dp[i][0]++;
		
		for(int j = 1; j <= m; j++){
			dp[0][j] = dp[0][j-1];
			if(spref2[0] <= d2[j-1].s1) dp[0][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 <= d1[i-1].s1) c2++;
			dp[i][j] = max(c1, c2);
		}
	}

	cout << dp[n][m];
	return 0;
}
#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...