Submission #898011

#	Time	Username	Problem	Language	Result	Execution time	Memory
898011		vlnt32	Cloud Computing (CEOI18_clo)	C++14	100 / 100	1344 ms	25760 KiB

clo

#include <bits/stdc++.h>
#define problem "test"
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) (v).resize(unique(ALL(v)) - (v).begin())
#define BIT(x,i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
using namespace std;
const int N = 2000;

template<class X,class Y>
    bool maximize(X &x,Y y){
        if (x < y){
            x = y;    return true;
        }
        return false;
    }

template<class X,class Y>
    bool minimize(X &x,Y y){
        if (x > y){
            x = y;    return true;
        }
        return false;
    }

struct State{
    ll c,f,v;
    State (ll _c = 0,ll _f = 0,ll _v = 0){
        c = _c, f = _f, v = _v;
    }
    void input(){
        cin>>c>>f>>v;
    }
    bool operator < (const State &other) const{
        return f > other.f;
    }
};

int n,m;
State cpt[N + 5],person[N + 5];
ll maxCore,maxF;

namespace subtask1{
    const int nMax = 15;
    const int sMax = 750;
    ll dp[2][N + 5][sMax + 5],oo;

    void process(){
        int sumMax = 0;
        for (int i=1;i<= n;i++ )
            sumMax += cpt[i].c;
        memset(dp,-0x3f,sizeof(dp));
        oo = dp[0][0][0];
        dp[0][0][0] = 0;
        for (int i=0;i<= n;i++ ){
            memset(dp[(i + 1) & 1],-0x3f,sizeof(dp[(i + 1) & 1]));
            for (int j=0;j<= m;j++ )
                for (int cnt=0;cnt<= sumMax;cnt++ )
                    if (dp[i & 1][j][cnt] != oo){
                        if (j < m && person[j + 1].f <= cpt[i].f && person[j + 1].c <= cnt)
                            maximize(dp[i & 1][j + 1][cnt - person[j + 1].c],dp[i & 1][j][cnt] + person[j + 1].v);
                        if (i < n && cnt + cpt[i + 1].c <= sumMax)
                            maximize(dp[(i + 1) & 1][j][cnt + cpt[i + 1].c],dp[i & 1][j][cnt] - cpt[i + 1].v);
                        maximize(dp[(i + 1) & 1][j][cnt],dp[i & 1][j][cnt]);
                        maximize(dp[i & 1][j + 1][cnt],dp[i & 1][j][cnt]);
                        maximize(dp[(i + 1) & 1][j + 1][cnt],dp[i & 1][j][cnt]);
                    }
        }
        ll res = oo;
        for (int cnt=0;cnt<= sumMax;cnt++ )
            maximize(res,dp[n & 1][m][cnt]);
        cout<<res;
    }
};

namespace subtask2{
    const int nMax = 15;
    const int sMax = 750;
    ll dp[2][nMax + 5][sMax + 5],oo;

    void process(){
        int sumMax = 0;
        for (int i=1;i<= n;i++ )
            sumMax += person[i].c;
        memset(dp,-0x3f,sizeof(dp));
        oo = dp[0][0][0];
        dp[0][0][0] = 0;
        for (int i=0;i<= n;i++ ){
            memset(dp[(i + 1) & 1],-0x3f,sizeof(dp[(i + 1) & 1]));
            for (int j=0;j<= m;j++ )
                for (int cnt=0;cnt<= sumMax;cnt++ )
                    if (dp[i & 1][j][cnt] != oo){
                        if (j < m && person[j + 1].f <= cpt[i].f && person[j + 1].c <= cnt)
                            maximize(dp[i & 1][j + 1][cnt - person[j + 1].c],dp[i & 1][j][cnt] + person[j + 1].v);
                        if (i < n){
                            int newCnt = (cnt + cpt[i + 1].c >= sumMax ? sumMax : cnt + cpt[i + 1].c);
                            maximize(dp[(i + 1) & 1][j][newCnt],dp[i & 1][j][cnt] - cpt[i + 1].v);
                        }
                        maximize(dp[(i + 1) & 1][j][cnt],dp[i & 1][j][cnt]);
                        maximize(dp[i & 1][j + 1][cnt],dp[i & 1][j][cnt]);
                        maximize(dp[(i + 1) & 1][j + 1][cnt],dp[i & 1][j][cnt]);
                    }
        }
        ll res = oo;
        for (int cnt=0;cnt<= sumMax;cnt++ )
            maximize(res,dp[n & 1][m][cnt]);
        cout<<res;
    }
};

namespace subtask3{
    const int nMax = 2000;
    ll dp[nMax + 5][nMax + 5],oo;

    void process(){
        for (int i=1;i<= n;i++ )
            for (int j=1;j<= m;j++ ){
                dp[i][j] = max({dp[i][j - 1],dp[i - 1][j],dp[i - 1][j - 1]});
                if (cpt[i].f >= person[j].f)
                    dp[i][j] = max(dp[i][j],dp[i - 1][j - 1] + person[j].v - cpt[i].v);
            }

        cout<<dp[n][m];
    }
}

namespace subtask4{
    const int sumMax = 1e5;

    ll maxValue[sumMax + 5],minCost[sumMax + 5],oo;

    void process(){
        int sumCpt = 0;
        for (int i=1;i<= n;i++ )
            sumCpt += cpt[i].c;
        memset(minCost,0x3f,sizeof(minCost));
        minCost[0] = 0;

        for (int i=1;i<= n;i++ )
            for (int cnt=sumCpt;cnt>= cpt[i].c;cnt-- )
                minimize(minCost[cnt],minCost[cnt - cpt[i].c]  + cpt[i].v);

        int sumPer = 0;
        for (int i=1;i<= m;i++ )
            sumPer += person[i].c;
        memset(maxValue,-0x3f,sizeof(maxValue));
        oo = maxValue[0];
        maxValue[0] = 0;

        for (int i=1;i<= m;i++ )
            for (int cnt=sumPer;cnt>= person[i].c;cnt-- )
                maximize(maxValue[cnt],maxValue[cnt - person[i].c] + person[i].v);

        for (int i=sumCpt;i>= 0;i-- )
            minimize(minCost[i],minCost[i + 1]);

        ll res = 0;

        for (int i=0;i<= min(sumCpt,sumPer);i++ )
            if (maxValue[i] != oo)
                res = max(res,maxValue[i] - minCost[i]);

        cout<<res;
    }
};

namespace subtask6{
    const int nMax = 2000;
    const int cMax = 100;
    ll dp[2][nMax + 5][cMax + 5],oo;

    void process(){
        memset(dp,-0x3f,sizeof(dp));
        oo = dp[0][0][0];
        dp[0][0][0] = 0;
        for (int i=0;i<= n;i++ ){
            memset(dp[(i + 1) & 1],-0x3f,sizeof(dp[(i + 1) & 1]));
            for (int j=0;j<= m;j++ )
                for (int cnt=0;cnt<= 100;cnt++ )
                    if (dp[i & 1][j][cnt] != oo){
                        if (j < m && person[j + 1].f <= cpt[i].f && person[j + 1].c <= cnt)
                            maximize(dp[i & 1][j + 1][cnt - person[j + 1].c],dp[i & 1][j][cnt] + person[j + 1].v);
                        if (i < n && cnt + cpt[i + 1].c <= cMax){
                            int newCnt = (cnt + cpt[i + 1].c);
                            maximize(dp[(i + 1) & 1][j][newCnt],dp[i & 1][j][cnt] - cpt[i + 1].v);
                        }
                        maximize(dp[(i + 1) & 1][j][cnt],dp[i & 1][j][cnt]);
                        maximize(dp[i & 1][j + 1][cnt],dp[i & 1][j][cnt]);
                        maximize(dp[(i + 1) & 1][j + 1][cnt],dp[i & 1][j][cnt]);
                    }
        }
        ll res = 0;
        for (int cnt=0;cnt<= 100;cnt++ )
            maximize(res,dp[n & 1][m][cnt]);
        cout<<res;
    }
};

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);    cout.tie(NULL);
    cin>>n;
    for (int i=1;i<= n;i++ ){
        cpt[i].input();
        maxCore = max(maxCore,cpt[i].c);
        maxF = max(maxF,cpt[i].f);
    }
    cin>>m;
    for (int i=1;i<= m;i++ ){
        person[i].input();
        maxCore = max(maxCore,person[i].c);
        maxF = max(maxF,person[i].f);
    }

    sort(cpt + 1,cpt + n + 1);
    sort(person + 1,person + m + 1);

    if (n <= 15)
        subtask1 :: process();
    else if (m <= 15)
        subtask2 :: process();
    else if (maxCore == 1)
        subtask3 :: process();
    else if (maxF == 1)
        subtask4 :: process();
    else subtask6 :: process();
}

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