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 <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 2000 + 10;
const llong INF = 1e18;
int n, m;
struct Dish
{
int time;
llong limit;
int reward;
int idx;
bool type;
};
Dish a[MAXN];
Dish b[MAXN];
llong prefixA[MAXN];
llong prefixB[MAXN];
llong dp[MAXN][MAXN];
bool bl[MAXN][MAXN];
llong f(int aPos, int bPos)
{
if (aPos == n + 1 && bPos == m + 1)
{
return 0;
}
if (bl[aPos][bPos])
{
return dp[aPos][bPos];
}
bl[aPos][bPos] = true;
dp[aPos][bPos] = -INF;
llong sum = prefixA[aPos - 1] + prefixB[bPos - 1];
if (aPos <= n)
{
dp[aPos][bPos] = std::max(dp[aPos][bPos], f(aPos + 1, bPos) + (sum + a[aPos].time <= a[aPos].limit ? a[aPos].reward : 0));
}
if (bPos <= m)
{
dp[aPos][bPos] = std::max(dp[aPos][bPos], f(aPos, bPos + 1) + (sum + b[bPos].time <= b[bPos].limit ? b[bPos].reward : 0));
}
return dp[aPos][bPos];
}
void solve()
{
for (int i = 1 ; i <= n ; ++i)
{
prefixA[i] = prefixA[i - 1] + a[i].time;
}
for (int i = 1 ; i <= m ; ++i)
{
prefixB[i] = prefixB[i - 1] + b[i].time;
}
for (int i = 1 ; i <= n ; ++i)
{
for (int j = 1 ; j < m ; ++j)
{
assert(f(i, j) >= f(i, j + 1));
// std::cout << f(i, j) << ' ';
}
// std::cout << '\n';
}
std::cout << f(1, 1) << '\n';
}
void input()
{
std::cin >> n >> m;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i].time >> a[i].limit >> a[i].reward;
a[i].idx = i;
a[i].type = false;
}
for (int i = 1 ; i <= m ; ++i)
{
std::cin >> b[i].time >> b[i].limit >> b[i].reward;
b[i].idx = i;
a[i].type = true;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
# | 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... |