제출 #1050544

#제출 시각아이디문제언어결과실행 시간메모리
1050544nghiaaaCloud Computing (CEOI18_clo)C++17
0 / 100
62 ms109652 KiB
#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 = 20;
struct item{
    int 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;
bool ready[N + 1][N + 1][50][2];
int dp[N + 1][N + 1][40][2];
const ll inf = 1e9;
ll f(int i, int j, int cores, bool done)
{
    if (i == 3 && j == 1 && cores == 1 && done == true)
    {
        cerr << "";
    }
    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, 0, 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(pre1, pre2);
    }
    else{
        int nxtcores = cores;
        if (shop[i - 1].cl_rate < order[j + 1].cl_rate)
            nxtcores = 0;
        if (!done){
            ll pre1 = f(i, j, order[j].cores + cores, 1) + order[j].price;
            ll pre2 = f(i, j + 1, nxtcores, 0);
            return dp[i][j][cores + UP][done] = max(pre1, pre2);
        }
        else{
            return dp[i][j][cores + UP][done] = f(i, j + 1, nxtcores, 0);
        }
    }
}
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);
    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 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...