Submission #698283

#	Time	Username	Problem	Language	Result	Execution time	Memory
698283		Duy_e	Cloud Computing (CEOI18_clo)	C++14	100 / 100	706 ms	2100 KiB

clo

#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
#define rep(i, n, m) for (ll i = n; i <= m; i ++)
#define rrep(i, n, m) for (ll i = n; i >= m; i --)
#define file "test"
using namespace std;

const long long N = 2e5 + 7;
const long long INF = 1e18;
const long long MOD = 2e9 + 11;
const long long base = 311;

ll n, m, dp[2][N];
struct clo {
    ll c, f, v, t;
    bool operator <(clo other) {
        if (f == other.f) {
            if (t == other.t)
                return v < other.v;
            return t < other.t;
        }
        return f > other.f;
    }
} a[N];

void maximize(ll &x, ll y) {
    if (y > x) x = y;
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        //freopen(file".inp", "r", stdin);
        //freopen(file".out", "w", stdout);
    #endif // ONLINE_JUDGE

    cin >> n;
    ll mx = 0;
    rep(i, 1, n) {
        cin >> a[i].c >> a[i].f >> a[i].v;
        a[i].t = 0;
        mx += a[i].c;
    }
    cin >> m;
    rep(i, n + 1, m + n) {
        cin >> a[i].c >> a[i].f >> a[i].v;
        a[i].t = 1;
    }

    sort(a + 1, a + 1 + n + m);
    rep(i, 0, mx) dp[1][i] = dp[0][i] = -INF;
    dp[0][0] = 0;
    rep(i, 1, n + m) {
        ll val = 0, add = 0;
        if (a[i].t == 0)
            val = -a[i].v, add = a[i].c;
        else
            val = a[i].v, add = -a[i].c;

        rep(j, 0, mx) dp[1][j] = dp[0][j];
        rep(j, 0, mx)
            if (j + add <= mx && j + add >= 0)
                maximize(dp[1][j + add], dp[0][j] + val);
        rep(j, 0, mx) dp[0][j] = dp[1][j];
    }

    ll ans = 0;
    rep(i, 0, mx) ans = max(ans, dp[1][i]);
    cout << ans;
    return 0;
}

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