Submission #77939

#	Time	Username	Problem	Language	Result	Execution time	Memory
77939		Saboon	Cloud Computing (CEOI18_clo)	C++14	36 / 100	392 ms	3348 KiB

clo

#include <iostream>
#include <queue>
#include <bitset>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int inf = 1e9 + 100;
const int maxn = 2e5 + 100;

int n, m;

ll c[maxn], f[maxn], v[maxn], C[maxn], F[maxn], V[maxn];

ll dp[maxn], di[maxn];

int d[maxn], q[maxn];
bool cmp (int fi, int se) {
    return f[fi] >= f[se];
}

bool cmp2 (int fi, int se) {
    return F[fi] >= F[se];
}

ll a[300][300];

void solve_just_for_c () {
    for (int i = 1; i <= n; i++)
        d[i] = i - 1;
    for (int i = 1; i <= m; i++)
        q[i] = i - 1;
    sort (d + 1, d + n + 1, cmp);
    sort (q + 1, q + m + 1, cmp2);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = max (a[i][j - 1], a[i - 1][j]);
            for (int k = j; k >= 1; k--) {
                if (f[d[i]] >= F[q[k]])
                    a[i][j] = max (a[i][j], a[i - 1][k - 1] + V[q[k]] - v[d[i]]);
            }
        }
    }
    cout << a[n][m] << endl;
    exit (0);
}

void solve_just_for_f () {
    memset (dp, 63, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = n * 50; j >= c[i]; j--) {
            dp[j] = min (dp[j], dp[j - c[i]] + v[i]);
        }
    }
    for (int i = n - 1; i >= 0; i--)
        dp[i] = min (dp[i], dp[i + 1]);

    di[0] = 0;
    for (int i = 0; i < m; i++) {
        for (int j = n * 50; j >= C[i]; j--) {
            di[j] = max (di[j], di[j - C[i]] + V[i]);
        }
    }
    ll ans = 0;
    for (int i = 0; i <= 50 * n; i++)
        ans = max (ans, di[i] - dp[i]);
    cout << ans << endl;
    exit (0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    bool found = 0;
    for (int i = 0; i < n; i++) {
        cin >> c[i] >> f[i] >> v[i];
        if (c[i] != 1)
            found = 1;
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> C[i] >> F[i] >> V[i];
        if (C[i] != 1)
            found = 1;
    }
    if (n <= 250 and m <= 250 and !found)
        solve_just_for_c ();
    solve_just_for_f ();
}

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