제출 #132077

#제출 시각아이디문제언어결과실행 시간메모리
132077SirCenessTwo Dishes (JOI19_dishes)C++14
10 / 100
1337 ms93484 KiB
#include <bits/stdc++.h>

using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l%&&r<=sr
#define outside sr<l||r<sl

typedef long long ll;

struct node {
	ll a, b, top;
};

node a[200002];
node b[200002];
int n, m;
ll dp[2002][2002];

ll get(int kim, int dayi){
	if (dayi == -1) return 0;
	else if (kim == 0) return a[dayi].top;
	else return b[dayi].top;
}

int main(){
	cin >> n >> m;
	ll cur = 0;
	for (int i = 0; i < n; i++){
		ll x, y, c;
		cin >> x >> y >> c;
		cur += x;
		a[i] = {x, y, cur};
	}
	cur = 0;
	for (int i = 0; i < m; i++){
		ll x, y, c;
		cin >> x >> y >> c;
		cur += x;
		b[i] = {x, y, cur};
	}
	
	for (int i = 0; i <= n; i++) 
	for (int j = 0; j <= m; j++)
	dp[i][j] = -1;
	
	dp[0][0] = 0;
	for (int i = 0; i <= n; i++){
		for (int j = 0; j <= m; j++){
			//cout << dp[i][j] << " ";
			if (i != n) dp[i+1][j] = max(dp[i+1][j], dp[i][j] + ((get(0, i) + get(1, j-1) <= a[i].b) ? 1 : 0));
			if (j != m) dp[i][j+1] = max(dp[i][j+1], dp[i][j] + ((get(0, i-1) + get(1, j) <= b[j].b) ? 1 : 0));
		}
		//cout << endl;
	}
	//cout << endl;
	
	cout << dp[n][m] << endl;
	
}
#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...