Submission #675537

#	Time	Username	Problem	Language	Result	Execution time	Memory
675537		omikron123	Cloud Computing (CEOI18_clo)	C++14	100 / 100	712 ms	2004 KiB

clo

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <cstdint>
using namespace std;
typedef long long ll;

// 1. 把computer和order放在一起处理，按频率排序，一个大列表。
// 2. dp[i][j]，使用前i个的transaction的时候，如果剩下j个core时，最大的profit

// n,m <= 2000
int n, m;
struct T {
    int c, f, v;
};
T tr[4005];
bool cmp(T &a, T &b) {
    if (a.f == b.f) 
        return a.c > b.c;       // computers before orders
    else
        return a.f > b.f;
}
int C;      // total cores

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &tr[i].c, &tr[i].f, &tr[i].v);
        tr[i].v = -tr[i].v; // computers consume profit
        C += tr[i].c;
    }
    scanf("%d", &m);
    for (int i = n+1; i <= n+m; i++) {
        scanf("%d %d %d", &tr[i].c, &tr[i].f, &tr[i].v);
        tr[i].c = -tr[i].c; // orders consume cores
    }
    sort(tr+1, tr+n+m+1, cmp);      // sort by decreasing frequency

    vector<ll> dp(C+1, INT64_MIN), DP;
    ll ans = 0;
    dp[0] = 0;
    for (int i=1; i <= n+m; i++) {
        DP = dp;
        for (int j=0; j <= C; j++) {
            int J = j - tr[i].c;
            if (J >= 0 && J <= C && dp[J] != INT64_MIN)
                DP[j] = max(DP[j], dp[J] + tr[i].v);
            if (i == n+m)
                ans = max(ans, DP[j]);
        }
        swap(dp,DP);
    }
    printf("%lld", ans);

    return 0;
}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
clo.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d %d %d", &tr[i].c, &tr[i].f, &tr[i].v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d", &m);
      |     ~~~~~^~~~~~~~~~
clo.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d %d %d", &tr[i].c, &tr[i].f, &tr[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