Submission #1050716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050716		nghiaaa	Cloud Computing (CEOI18_clo)	C++17	0 / 100	29 ms	51036 KiB

clo

#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{
    int cores, cl_rate;
    ll 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[17][N + 1][101][2];
bool ready[17][N + 1][101][2];
const ll inf = 1e15;
ll f(int i, int j, int cores, bool done)
{
    if (j == m + 1){
        if (cores <= 0) return 0;
        return -inf;
    }
    if (ready[i][j][cores + UP][done])
        return dp[i][j][cores + UP][done];
    ready[i][j][cores + UP][done] = 1;
    if (i == n + 1)
    {
        if (cores > 0) return -inf;
        if (done)
            return dp[i][j][cores + UP][done] = max(0LL, f(i, j + 1, cores, 0));
        else{
            if (shop[i - 1].cl_rate < order[j].cl_rate)
                return 0;
            ll pre1 = f(i, j + 1, cores + order[j].cores, 0);
            ll pre2 = f(i, j + 1, cores, 0);
            if (pre1 != -inf)
                pre1 += order[j].price;
            return dp[i][j][cores + UP][done] = max({0LL, pre1, pre2});
        }
    }
    if (shop[i].cl_rate < order[j].cl_rate)
    {
        assert(cores >= 0);
        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);
            ll pre2 = f(i, j + 1, nxtcores, 0);
            if (pre1 != -inf) pre1 += order[j].price;
            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;
    cin >> m;
    forw(i, 1, m)
        cin >> order[i].cores >> order[i].cl_rate >> order[i].price;
    sort(shop + 1, shop + n + 1);
    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;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 18
• Subtask 3: 0 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10