Submission #467033

#	Time	Username	Problem	Language	Result	Execution time	Memory
467033		Qw3rTy	Cloud Computing (CEOI18_clo)	C++11	100 / 100	1855 ms	2252 KiB

clo

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxN = 2e3+5;
const int maxC = 50+5;

struct ds{
    int c,f,v;
    bool order;
    ds(){};
    ds(int c, int f, int v, bool order){
        this -> c = c;
        this -> f = f;
        this -> v = v;
        this -> order = order;
    }
}a[maxN<<1];

bool cmp(ds a, ds b){
    return a.f > b.f;
}

int N,M;
int cnt = 0;
int f[2][maxN*maxC]; //f[i][j] = max profit given first i items and j cores with frequency higher than current
int maxF = 0;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("../test.in","r",stdin);
    cin >> N;
    for(int i = 1; i <= N; ++i){
        int c,f,v; cin >> c >> f >> v;
        a[++cnt] = ds(c,f,v,false);
        maxF = max(maxF,f);
    }
    cin >> M;
    for(int i = 1; i <= M; ++i){
        int c,f,v; cin >> c >> f >> v;
        if(f > maxF)continue;
        a[++cnt] = ds(c,f,v,true);
    }
    //Put computers first if all freq == 1
    if(maxF != 1)sort(a+1,a+cnt+1,cmp);
    memset(f,0x80,sizeof(f));
    //Initial state
    f[0][0] = 0;
    f[1][0] = 0;
    for(int i = 1; i <= cnt; ++i){
        for(int j = 0; j <= N*50; ++j){
            //Invalid state
            if(f[0][j] < -1e16)continue;
            //Ignore the current item
            f[1][j] = max(f[1][j],f[0][j]);
            //Consider the current item
            if(a[i].order == true){
                //Not enough cores for the current order
                if(j < a[i].c)continue;
                f[1][j-a[i].c] = max(f[0][j-a[i].c], f[0][j] + a[i].v);
            }
            else{
                assert(j+a[i].c <= N*50);
                f[1][j+a[i].c] = max(f[0][j+a[i].c], f[0][j] - a[i].v);
            }
        }
        swap(f[0],f[1]);
        memset(f[1],0x80,sizeof(f[1]));
        f[1][0] = 0;
//        for(int j = 0; j <= 20; ++j){
//            if(f[0][j] < -1e16)cout << "/" << " ";
//            else cout << f[0][j] << " ";
//        }
//        cout << '\n';
    }
    int res = 0;
    for(int i = 0; i <= N*50; ++i){
        res = max(res,f[0][i]);
    }
    cout << res << '\n';
}

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