This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |