Submission #217606

#	Time	Username	Problem	Language	Result	Execution time	Memory
217606		DystoriaX	Cloud Computing (CEOI18_clo)	C++14	100 / 100	413 ms	1284 KiB

clo

#include <bits/stdc++.h>

using namespace std;

struct node{
    int c, f, v;
};

int n, m;
const int MAX = 100001;
vector<node> comp, dem;
priority_queue<int, vector<int>, greater<int> > pq;
long long ans = 0, dp[MAX];

bool cp(node a, node b){
    return a.f > b.f;
}

int main(){
    scanf("%d", &n);

    comp.resize(n + 1);
    for(int i = 1; i <= n; i++) scanf("%d%d%d", &comp[i].c, &comp[i].f, &comp[i].v);

    scanf("%d", &m);

    dem.resize(m + 1);
    for(int i = 1; i <= m; i++) scanf("%d%d%d", &dem[i].c, &dem[i].f, &dem[i].v);

    sort(comp.begin() + 1, comp.end(), cp);
    sort(dem.begin() + 1, dem.end(), cp);

    //dp = maxProfit
    for(int i = 0; i < MAX; i++) dp[i] = -1e18;

    dp[0] = 0;
    
    int idx = 1;
    for(int i = 1; i <= m; i++){
        while(idx <= n && comp[idx].f >= dem[i].f){
            for(int k = MAX - 1; k >= comp[idx].c; k--){
                dp[k] = max(dp[k], dp[k - comp[idx].c] - comp[idx].v);

            }
            idx++;
        }

        for(int k = 0; k + dem[i].c < MAX; k++){
            dp[k] = max(dp[k], dp[k + dem[i].c] + dem[i].v);
        }
    }

    for(int i = 0; i < MAX; i++) ans = max(ans, dp[i]);

    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
clo.cpp:23:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d%d%d", &comp[i].c, &comp[i].f, &comp[i].v);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
clo.cpp:28:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= m; i++) scanf("%d%d%d", &dem[i].c, &dem[i].f, &dem[i].v);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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