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 ld long double
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define sz(a) (int)a.size()
#define len(a) (int)a.length()
const int mod = 998244353;
inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;}
//auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
//mt19937 RAND(seed);
inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;}
inline int mul(int u,int v){return (ll)u*v%mod;}
const int N = 2000;
const int UP = 50;
struct item{
ll cores, cl_rate, price;
item(){}
bool operator < (item &u) const
{
return cl_rate < u.cl_rate;
}
};
item shop[N + 1], order[N + 1];
int n, m;
//ll dp[N + 1][2][101][2];
ll dp[16][N + 1][101][2];
bool ready[16][N + 1][101][2];
const ll inf = 1e15;
ll f(int i, int j, int cores, bool done)
{
if (i == n + 1)
{
if (cores <= 0) return 0;
else return -inf;
}
if (j == m + 1) return 0;
if (ready[i][j][cores + UP][done])
return dp[i][j][cores + UP][done];
ready[i][j][cores + UP][done] = 1;
if (shop[i].cl_rate < order[j].cl_rate)
return dp[i][j][cores + UP][done] = f(i + 1, j, cores, done);
if (cores > 0)
{
ll pre1 = -shop[i].price + f(i + 1, j, cores - shop[i].cores, done);
ll pre2 = f(i + 1, j, cores, done);
return dp[i][j][cores + UP][done] = max({-inf, pre1, pre2});
}
else{
int nxtcores = cores, nxtcores2 = cores;
if (shop[i - 1].cl_rate < order[j + 1].cl_rate)
nxtcores = 0;
if (shop[i - 1].cl_rate < order[j].cl_rate)
nxtcores2 = 0;
if (!done){
ll pre1 = f(i, j, order[j].cores + nxtcores2, 1) + order[j].price;
ll pre2 = f(i, j + 1, nxtcores, 0);
return dp[i][j][cores + UP][done] = max({-inf, pre1, pre2});
}
else{
return dp[i][j][cores + UP][done] = f(i, j + 1, nxtcores, 0);
}
}
}
//void nomorerecursion()
//{
// ford(j, m + 1, 1) ford(i, n + 1, 1) ford(cores, 50, -50) ford(done, 1, 0)
// {
// if (i == 1 && j == 1 && cores == 0 && done == 0)
// {
// cerr << "";
// }
// ll &f = dp[i][j & 1][cores + UP][done];
// if (i == n + 1)
// {
// if (cores <= 0) f = 0;
// else f = -inf;
// }
// else if (j == m + 1) f = 0;
// else if (shop[i].cl_rate < order[j].cl_rate)
// f = dp[i + 1][j & 1][0 + UP][done];
// else if (cores > 0)
// {
// ll pre1 = -shop[i].price + dp[i + 1][j & 1][cores - shop[i].cores + UP][done];
// ll pre2 = dp[i + 1][j & 1][cores + UP][done];
// f = max({-inf, pre1, pre2});
// }
// else {
// int nxtcores = cores;
// if (j < m && shop[i - 1].cl_rate < order[j + 1].cl_rate)
// nxtcores = 0;
// if (!done){
// ll pre1 = dp[i][j & 1][order[j].cores + cores + UP][1] + order[j].price;
// ll pre2 = dp[i][(j + 1) & 1][nxtcores + UP][0];
// f = max({-inf, pre1, pre2});
// }
// else{
// f = dp[i][(j + 1) & 1][nxtcores + UP][0];
// }
// }
// if (i == 1 && j == 1 && done == 0 && cores == 0)
// {
// cout << f;
// break;
// }
// }
//}
void solve()
{
cin >> n;
forw(i, 1, n)
cin >> shop[i].cores >> shop[i].cl_rate >> shop[i].price;
sort(shop + 1, shop + n + 1);
cin >> m;
forw(i, 1, m)
cin >> order[i].cores >> order[i].cl_rate >> order[i].price;
sort(order + 1, order + m + 1);
// nomorerecursion();
cout << f(1, 1, 0, 0);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("test.inp","r",stdin);
//freopen("test.out","w",stdout);
//time_t TIME_TU=clock();
int t=1;
// cin>>t;
while(t--)
solve();
//time_t TIME_TV=clock();
//cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
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... |