Submission #1276751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276751		herominhsteve	Cloud Computing (CEOI18_clo)	C++20	100 / 100	406 ms	3656 KiB

clo

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const long long INF = (long long) 1e16 + 15092007;

struct Computer{
    int c;
    long long f,price;
    Computer():c(0),f(0),price(0) {}
    Computer(int C,long long F,long long P):c(C),f(F),price(P) {}
    bool operator < (const Computer &other) const{
        return f > other.f;
    }
};

int n,m;
vector<Computer> comp;
vector<Computer> order;
int totalC;

void init(){
	cin>>n;
    comp.resize(n);
    for (Computer &x : comp) cin>>x.c>>x.f>>x.price, totalC+=x.c;
    cin>>m;
    order.resize(m);
    for (Computer &x : order) cin>>x.c>>x.f>>x.price,totalC+=x.c;
}

void sol(){
	sort(allof(comp));
    sort(allof(order));

    // ? dp[c]: maximum profit when we have c available cores
    vector<long long> dp(totalC+1,-INF);
    dp[0] = 0;
    int ptr=0;
    int curMaxC=0;

    for (int i=0;i<m;i++){
        while (ptr < n and comp[ptr].f >= order[i].f){
            int c = comp[ptr].c;
            long long price = comp[ptr].price;
            for (int k = curMaxC; k >= 0; k--){
                if (dp[k] == -INF) continue;
                maximize(dp[k + c], dp[k] - price);
            }
            ptr++;
            curMaxC += c;
        }
        int need = order[i].c;
        long long get = order[i].price;
        if (need <= curMaxC){
            vector<long long> nxt = dp;
            for (int k = need; k <= curMaxC; k++){
                if (dp[k] == -INF) continue;
                maximize(nxt[k - need],dp[k] + get);
            }   
            dp.swap(nxt);
        }
    }
    
    long long res = 0;
    for (long long x : dp) maximize(res,x);
    cout<<res;
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

clo.cpp: In function 'void setup()':
clo.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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