제출 #1050572

#제출 시각아이디문제언어결과실행 시간메모리
1050572nghiaaaCloud Computing (CEOI18_clo)C++14
18 / 100
2238 ms6868 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 = 50;
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;
ll dp[N + 1][2][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, 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({-inf, 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({-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();
}
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...